Maximal and minimal vertex-critical graphs of diameter two (Q1127872)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Maximal and minimal vertex-critical graphs of diameter two
scientific article

    Statements

    Maximal and minimal vertex-critical graphs of diameter two (English)
    0 references
    0 references
    0 references
    10 September 1998
    0 references
    A graph is vertex-critical if deleting any vertex increases its diameter. We construct, for each \(\nu\geq 5\) except \(\nu= 6\), a vertex-critical graph of diameter two on \(\nu\) vertices with at least \(\frac 12\nu^2- \sqrt{2}\nu^{\frac 32}+ c_1\nu\) edges, where \(c_1\) is some constant. We show that such a graph contains at most \(\frac 12\nu^2- \frac{\sqrt{2}}{2} \nu^{\frac 32}+ c_2\nu\) edges, where \(c_2\) is some constant. We also construct, for each \(\nu\geq 5\) except \(\nu=6\), a vertex-critical graph of diameter two on \(\nu\) vertices with at most \(\frac 12 (5\nu-12)\) edges. We show such a graph must contain at least \(\frac 12 (5\nu-29)\) edges.
    0 references
    diameter
    0 references
    critical graph
    0 references
    number of edges
    0 references

    Identifiers