Name
Abstract | ||
|---|---|---|
In the context of the degree/diameter problem, the 'defect' of a graph represents the difference between the corresponding Moore bound and its order. Thus, a graph with maximum degree d and diameter two has defect two if its order is n=d^2-1. Only four extremal graphs of this type, referred to as (d,2,2)-graphs, are known at present: two of degree d=3 and one of degree d=4 and 5, respectively. In this paper we prove, by using algebraic and spectral techniques, that for all values of the degree d within a certain range, (d,2,2)-graphs do not exist. The enumeration of (d,2,2)-graphs is equivalent to the search of binary symmetric matrices A fulfilling that AJ\"n=dJ\"n and A^2+A+(1-d)I\"n=J\"n+B, where J\"n denotes the all-one matrix and B is the adjacency matrix of a union of graph cycles. In order to get the factorization of the characteristic polynomial of A in Q[x], we consider the polynomials F\"i\",\"d(x)=f\"i(x^2+x+1-d), where f\"i(x) denotes the minimal polynomial of the Gauss period @z\"i+@z\"i@?, being @z\"i a primitive ith root of unity. We formulate a conjecture on the irreducibility of F\"i\",\"d(x) in Q[x] and we show that its proof would imply the nonexistence of (d,2,2)-graphs for any degree d5. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1016/j.disc.2008.09.017 | Discrete Mathematics |
Keywords | Field | DocType |
defect,moore bound,cycle graph,characteristic polynomial,gauss period.,gauss period,symmetric matrices,minimal polynomial,maximum degree,adjacency matrix,roots of unity | Adjacency matrix,Discrete mathematics,Characteristic polynomial,Gauss,Combinatorics,Cycle graph,Root of unity,Minimal polynomial (linear algebra),Degree (graph theory),Function composition,Mathematics | Journal |
Volume | Issue | ISSN |
309 | 10 | Discrete Mathematics |
Citations | PageRank | References |
2 | 0.50 | 6 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| J. Conde | 1 | 17 | 2.77 |
| J. Gimbert | 2 | 30 | 3.65 |