Almost $K_m$-Saturated Graphs

MacDougall, James A. and Eggleton, Roger B. (1998) Almost $K_m$-Saturated Graphs. Congressus Numerantium, 131 . pp. 187-203.

PDF - Accepted Version
Download (170Kb) | Preview


    A graph is $K_m$-saturated if every possible addition of an edge creates a new $m$-clique. A graph is {\em almost} $K_m$-saturated if it is maximal with respect to not being $K_m$-saturated, that is, some edge can be added without creating a new $m$-clique, but a $K_m$-saturated graph results from any possible edge addition. The structure of almost $K_m$-saturated graphs is explicitly determined, and the almost $K_m$-saturated graphs of order $n$ are enumerated for $m = 3$ and 4. A graph is {\em locally almost} $K_m$-saturated if some edge addition does not create a $K_m$ but every two edge additions do. Every graph which is almost $K_m$-saturated has this local property, but so do others: the structure of such graphs is implicitly determined.

    Item Type: Article
    Subjects: 00-xx General
    Faculty: UNSPECIFIED
    Depositing User: Stephanie
    Date Deposited: 18 Nov 2010 12:06
    Last Modified: 18 Nov 2010 12:06

    Actions (login required)

    View Item