On the existence of graphs of diameter two and defect two (Q1025938): Difference between revisions

From MaRDI portal
Import240304020342 (talk | contribs)
Set profile property.
Set OpenAlex properties.
Property / full work available at URL
 
Property / full work available at URL: https://doi.org/10.1016/j.disc.2008.09.017 / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W2032748226 / rank
 
Normal rank

Revision as of 22:38, 19 March 2024

scientific article
Language Label Description Also known as
English
On the existence of graphs of diameter two and defect two
scientific article

    Statements

    On the existence of graphs of diameter two and defect two (English)
    0 references
    23 June 2009
    0 references
    A \((d,2,2)\)-graph is a \(n\)-vertex graph of maximum degree \(d\) and diameter 2 for which \(n=d^2-1\). Only 4 such graphs are known, two with \(d=3\) and one for \(d=4,5\) each. It is shown that irreducibility in \(\mathbb{Q}[x]\) of the characteristic polynomial of certain binary symmetric matrices depending on \(d>5\) implies nonexistence of a \((d,2,2)\)-graph, and such irreducibility is conjectured to always hold. Using the mathematics software PARI the conjecture has been verified for all \(d=6,\ldots,50\).
    0 references
    Moore bound
    0 references
    Defect
    0 references
    cycle graph
    0 references
    characteristic polynomial
    0 references
    irreducible
    0 references
    Gauss period
    0 references
    0 references
    0 references

    Identifiers