Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8897901 | Linear Algebra and its Applications | 2018 | 13 Pages |
Abstract
The Moore bound M(k,g) is a lower bound on the order of k-regular graphs of girth g (denoted (k,g)-graphs). The excess e of a (k,g)-graph of order n is the difference e=nâM(k,g). A (k,g)-cage is a (k,g)-graph with the fewest possible number of vertices. A graph of diameter d is said to be antipodal if, for any vertices u,v,w such that d(u,v)=d and d(u,w)=d, it follows that d(v,w)=d or v=w. Biggs and Ito proved that any (k,g)-cage of even girth g=2dâ¥6 and excess eâ¤kâ2 is a bipartite graph of diameter d+1. In this paper we treat (k,g)-cages of even girth and excess eâ¤kâ2. Based on spectral analysis we give a relation between the eigenvalues of the adjacency matrix A and the distance matrix Ad+1 of such cages. Applying matrix theory, we prove the non-existence of antipodal (k,g)-cages of excess e, for kâ¥e+2â¥4 and g=2dâ¥14.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Algebra and Number Theory
Authors
Slobodan Filipovski,