The smallest degree sum that yields potentially \(K_{r+1}-K_3\)-graphic sequences (Q2431967)

From MaRDI portal
scientific article
Language Label Description Also known as
English
The smallest degree sum that yields potentially \(K_{r+1}-K_3\)-graphic sequences
scientific article

    Statements

    The smallest degree sum that yields potentially \(K_{r+1}-K_3\)-graphic sequences (English)
    0 references
    24 October 2006
    0 references
    The paper has a theoretical aspect and its main purpose is to determine a value for \(\sigma(K_{r+1}-K_{r}, n)\) for \(n \geq 3r+5\). This number represents the smallest even integer such that each \(n\)-term graphic sequence \(\pi = (d_{1}, d_{2},\dots, d_{n})\) has a realization containing \(K_{r+1}-K_{3}\) as a subgraph. The author reminds in the introduction the notions regarding the sequence \(\pi\) to be potentially H-graphic or \(A_{r+1}\)-graphic. He also mentions the main results in this field for \(\sigma(K_{3}, n), \sigma(K_{4}, n), \sigma(K_{5}, n)\) and \(\sigma (K_{r+1} - e, n)\). Thus the article presents the proof of the fact that \(\sigma (K_{r+1} - K_{3}, n) = (r-1)(2n-r)-2(n-2)+2\) for \(r \geq 3\) and \(n \geq 3r+5\).
    0 references
    degree sequence
    0 references
    0 references

    Identifiers