Minimally Star-Saturated Graphs

MacDougall, James A. and Eggleton, Roger B. (2001) Minimally Star-Saturated Graphs. Congressus Numerantium, 149 . pp. 161-176.

PDF - Accepted Version
Download (403Kb) | Preview


    A simple graph $G$ is {\em minimally saturated} for $m$-stars if every edge added to $G$ creates a new star of order $m$, while every edge deleted from $G$ leaves a graph which no longer has that property. Such graphs are characterized for $m \geq 3$, several of their properties are deduced, and a recognition algorithm is given. The minimally saturated graphs for 3-stars and 4-stars are explicitly described. The {\em kernel} of a graph which is minimally saturated for $m$-stars is the subgraph induced by vertices of degree $m-2$. The kernels of maximal $m$-star-free graphs are characterized, and necessary or sufficient conditions are given for a graph to be a kernel of some graph which is minimally saturated for $m$-stars but not $m$-star-free.

    Item Type: Article
    Subjects: 00-xx General
    Faculty: UNSPECIFIED
    Depositing User: Stephanie
    Date Deposited: 13 Dec 2010 11:51
    Last Modified: 13 Dec 2010 11:51

    Actions (login required)

    View Item