Minimally Path-Saturated Graphs

MacDougall, James A. and Eggleton, Roger B. and Boswell, Sharon G. (1999) Minimally Path-Saturated Graphs. Congressus Numerantium, 138 . pp. 97-117.

PDF - Accepted Version
Download (317Kb) | Preview


    A finite or infinite graph $G$ is {\em minimally} $P_m$–{\em saturated} if every edge added to $G$ creates a new $m$–path, while every edge deleted from $G$ leaves a graph which no longer has that property. For $m = 3$ and 4 we determine all such graphs. For $m \geq 5$ we determine all minimally $P_m$–saturated cycles, paths and unions of paths. The minimal $P_m$–saturation thresholds for weight classes of caterpillars and related graphs are also determined. A convenient notation for finite trees is introduced to aid the exposition.

    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