Minimally triangle-saturated graphs: adjoining a single vertex

MacDougall, James A. and Eggleton, Roger B. (2002) Minimally triangle-saturated graphs: adjoining a single vertex. Australasian Journal of Combinatorics, 25 . pp. 263-278.

PDF - Accepted Version
Download (185Kb) | Preview


    A graph $G$ is triangle-saturated if every possible edge addition to $G$ creates one or more new triangles (3-cycles). Such a graph is minimally triangle-saturated if removal of any edge from $G$ leaves a graph that is not triangle-saturated. This paper investigates adding a single new vertex to a triangle-saturated graph so as to produce a new triangle-saturated graph, and determines the conditions under which the extended graph is minimally saturated. Particular attention is given to minimally saturated extensions which are {\em primitive} (no two vertices have the same neighbourhood). The results are applied to construct primitive maximal triangle-free graphs of every order $n \geq 9$.

    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