Uniquely \(K_r\)-saturated graphs (Q1953308)

From MaRDI portal
Revision as of 23:05, 18 April 2024 by Importer (talk | contribs) (‎Changed an Item)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
scientific article
Language Label Description Also known as
English
Uniquely \(K_r\)-saturated graphs
scientific article

    Statements

    Uniquely \(K_r\)-saturated graphs (English)
    0 references
    0 references
    0 references
    7 June 2013
    0 references
    Summary: A graph \(G\) is uniquely \(K_r\)-saturated if it contains no clique with \(r\) vertices and if for all edges \(e\) in the complement, \(G+e\) has a unique clique with \(r\) vertices. Previously, few examples of uniquely \(K_r\)-saturated graphs were known, and little was known about their properties. We search for these graphs by adapting orbital branching, a technique originally developed for symmetric integer linear programs. We find several new uniquely \(K_r\)-saturated graphs with \(4 \leq r \leq 7\), as well as two new infinite families based on Cayley graphs for \(\mathbb{Z}_n\) with a small number of generators.
    0 references
    uniquely saturated graphs
    0 references
    Cayley graphs
    0 references
    orbital branching
    0 references
    computational combinatorics
    0 references
    0 references
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references