On graphs with cyclic defect or excess

) 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

G_{d, k} (A) = J_{n} + B

(

G_{d, k} (A) = J_{n} - B

), where

A

denotes the adjacency matrix of the graph in question,

n

its order,

J_{n}

the

n i m e s n

matrix whose entries are all 1's,

B

the adjacency matrix of a union of vertex-disjoint cycles, and

G_{d, k} (x)

a polynomial with integer coefficients such that the matrix

G_{d, 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 emph{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 (f r a c 643 d^{3 / 2})

for the number of graphs of odd degree

d g e 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 g e 3

and cyclic defect or excess. Actually, we conjecture that, apart from the M"obius ladder on 8 vertices, no non-trivial graph of any degree

g e 3

and cyclic defect or excess exists.

Review text

Summary: 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 \(\varepsilon\) are called graphs with defect or excess \(\varepsilon\), respectively. While Moore graphs (graphs with \(\varepsilon=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 \(G_{d,k}(A)= J_n+B\) (\(G_{d,k}(A)= J_n-B\)), where \(A\) denotes the adjacency matrix of the graph in question, \(n\) its order, \(J_n\) the \(n\times n\) matrix whose entries are all 1's, \(B\) the adjacency matrix of a union of vertex-disjoint cycles, and \(G_{d,k}(x)\) a polynomial with integer coefficients such that the matrix \(G_{d,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(\frac{64}{3}d^{3/2})\) for the number of graphs of odd degree \(d\geq 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\geq 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 \(\geq 3\) and cyclic defect or excess exists.

Recommendations

Cited in

(10)

This page was built for publication: On graphs with cyclic defect or excess

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q612923)