Description:
We introduce the problem of finding the largest subgraph of a given weighted undirected graph (host graph), subject to constraints on the maximum degree and the diameter. We discuss some applications in security, network design and parallel processing, and in connection with the latter we derive some bounds for the order of the largest subgraph in host graphs of practical interest: the mesh and the hypercube. We also present a heuristic strategy to solve the problem, and we prove an approximation ratio for the algorithm. Finally, we provide some experimental results with a variety of host networks, which show that the algorithm performs better in practice than the prediction provided by our theoretical approximation ratio.
Description:
In 1960, Hoffman and Singleton investigated the existence of Moore graphs of diameter 2 (graphs of maximum degree d and d² + 1 vertices), and found that such graphs exist only for d = 2; 3; 7 and possibly 57. In 1980, Erdös et al., using eigenvalue analysis, showed that, with the exception of C4, there are no graphs of diameter 2, maximum degree d and d² vertices. In this paper, we show that graphs of diameter 2, maximum degree d and d² - 1 vertices do not exist for most values of d with d ≥ 6, and conjecture that they do not exist for any d ≥ 6.
Description:
The degree-diameter problem asks for the maximum number of vertices in a graph with maximum degree ∆ and diameter k. For fixed k, the answer is
Description:
A cubical polytope is a polytope with all its facets being combinatorially equivalent to cubes. We deal with the connectivity of the graphs of cubical polytopes. We first establish that, for any d >= 3, the graph of a cubical d-polytope with minimum degree 5 is min{delta, 2d - 2}-connected. Second, we show, for any d >= 4, that every minimum separator of cardinality at most 2d - 3 in such a graph consists of all the neighbours of some vertex and that removing the vertices of the separator from the graph leaves exactly two components, with one of them being the vertex itself. (C) 2019 Elsevier Inc. All rights reserved.
Description:
A cubical polytope is a polytope with all its facets being combinatorially equivalent to cubes. We deal with the connectivity of the graphs of cubical polytopes. We first establish that, for any d >= 3, the graph of a cubical d-polytope with minimum degree 5 is min{delta, 2d - 2}-connected. Second, we show, for any d >= 4, that every minimum separator of cardinality at most 2d - 3 in such a graph consists of all the neighbours of some vertex and that removing the vertices of the separator from the graph leaves exactly two components, with one of them being the vertex itself. (C) 2019 Elsevier Inc. All rights reserved.
Description:
In 1855 H. J. S. Smith proved Fermat's two-square using the notion of palindromic continuants. In his paper, Smith constructed a proper representation of a prime number
Description:
In 1855 H. J. S. Smith proved Fermat's two-square using the notion of palindromic continuants. In his paper, Smith constructed a proper representation of a prime number
Description:
We consider graphs of maximum degree 3, diameter D≥2 and at most 4 vertices less than the Moore bound M3,D, that is, (3,D,−)-graphs for ≤4. We prove the non-existence of (3,D,−4)-graphs for D≥5, completing in this way the catalogue of (3,D,−)-graphs with D≥2 and ≤4. Our results also give an improvement to the upper bound on the largest possible number N3,D of vertices in a graph of maximum degree 3 and diameter D, so that N3,D≤M3,D−6 for D≥5. Copyright Elsevier.
Description:
We consider graphs of maximum degree 3, diameter D≥2 and at most 4 vertices less than the Moore bound M3,D, that is, (3,D,−)-graphs for ≤4. We prove the non-existence of (3,D,−4)-graphs for D≥5, completing in this way the catalogue of (3,D,−)-graphs with D≥2 and ≤4. Our results also give an improvement to the upper bound on the largest possible number N3,D of vertices in a graph of maximum degree 3 and diameter D, so that N3,D≤M3,D−6 for D≥5. Copyright Elsevier.
Description:
It is well known that apart from the Petersen graph there are no Moore graphs of degree 3. As a cubic graph must have an even number of vertices, there are no graphs of maximum degree 3 and
Description:
The Moore bound constitutes both an upper bound on the order of a graph of maximum degree d and diameter D = k and a lower bound on the order of a graph of minimum degree d and odd girth g = 2k + 1. Graphs missing or exceeding the Moore bound by ε are called graphs with defect or excess ε, respectively. While Moore graphs (graphs with ε = 0) and graphs with defect or excess 1 have been characterized almost completely, graphs with defect or excess 2 represent a wide unexplored area. Graphs with defect (excess) 2 satisfy the equation Gd,k(A) = Jn +B (Gd,k(A) = Jn - B), where A denotes the adjacency matrix of the graph in question, n its order, Jn the n × n matrix whose entries are all 1's, B the adjacency matrix of a union of vertex-disjoint cycles, and Gd,k(x) a polynomial with integer coefficients such that the matrix Gd,k(A) gives the number of paths of length at most k joining each pair of vertices in the graph. In particular, if B is the adjacency matrix of a cycle of order n we call the corresponding graphs graphs with cyclic defect or excess; these graphs are the subject of our attention in this paper. We prove the non-existence of infinitely many such graphs. As the highlight of the paper we provide the asymptotic upper bound of O(64/3 d3/2) for the number of graphs of odd degree d ≥ 3 and cyclic defect or excess. This bound is in fact quite generous, and as a way of illustration, we show the non-existence of some families of graphs of odd degree d ≥ 3 and cyclic defect or excess. Actually, we conjecture that, apart from the Möbius ladder on 8 vertices, no non-trivial graph of any degree ≥ 3 and cyclic defect or excess exists.
Description:
The Moore bound constitutes both an upper bound on the order of a graph of maximum degree d and diameter D = k and a lower bound on the order of a graph of minimum degree d and odd girth g = 2k + 1. Graphs missing or exceeding the Moore bound by ε are called graphs with defect or excess ε, respectively. While Moore graphs (graphs with ε = 0) and graphs with defect or excess 1 have been characterized almost completely, graphs with defect or excess 2 represent a wide unexplored area. Graphs with defect (excess) 2 satisfy the equation Gd,k(A) = Jn +B (Gd,k(A) = Jn - B), where A denotes the adjacency matrix of the graph in question, n its order, Jn the n × n matrix whose entries are all 1's, B the adjacency matrix of a union of vertex-disjoint cycles, and Gd,k(x) a polynomial with integer coefficients such that the matrix Gd,k(A) gives the number of paths of length at most k joining each pair of vertices in the graph. In particular, if B is the adjacency matrix of a cycle of order n we call the corresponding graphs graphs with cyclic defect or excess; these graphs are the subject of our attention in this paper. We prove the non-existence of infinitely many such graphs. As the highlight of the paper we provide the asymptotic upper bound of O(64/3 d3/2) for the number of graphs of odd degree d ≥ 3 and cyclic defect or excess. This bound is in fact quite generous, and as a way of illustration, we show the non-existence of some families of graphs of odd degree d ≥ 3 and cyclic defect or excess. Actually, we conjecture that, apart from the Möbius ladder on 8 vertices, no non-trivial graph of any degree ≥ 3 and cyclic defect or excess exists.
Description:
It is known that the Moore bipartite bound provides an upper bound on the order of a connected bipartite graph. In this paper we deal with bipartite graphs of maximum degree
Description:
It is known that the Moore bipartite bound provides an upper bound on the order of a connected bipartite graph. In this paper we deal with bipartite graphs of maximum degree
Description:
For a d-dimensional polytope with v vertices, d + 1 <= v <= 2d, we calculate precisely the minimum possible number of m-dimensional faces, when m = 1 or m >= 0.62d. This confirms a conjecture of Grunbaum, for these values of m. For v = 2d + 1, we solve the same problem when m = 1 or d - 2; the solution was already known for m = d - 1. In all these cases, we give a characterisation of the minimising polytopes. We also show that there are many gaps in the possible number of m-faces: for example, there is no polytope with 80 edges in dimension 10, and a polytope with 407 edges can have dimension at most 23.
Description:
For a d-dimensional polytope with v vertices, d + 1 <= v <= 2d, we calculate precisely the minimum possible number of m-dimensional faces, when m = 1 or m >= 0.62d. This confirms a conjecture of Grunbaum, for these values of m. For v = 2d + 1, we solve the same problem when m = 1 or d - 2; the solution was already known for m = d - 1. In all these cases, we give a characterisation of the minimising polytopes. We also show that there are many gaps in the possible number of m-faces: for example, there is no polytope with 80 edges in dimension 10, and a polytope with 407 edges can have dimension at most 23.