Triangle-free and Triangle-saturated Graphs

MacDougall, James A. and Eggleton, Roger B. (1997) Triangle-free and Triangle-saturated Graphs. Journal of Combinatorial Mathematics and Combinatorial Computing, 25 . pp. 3-21.

PDF - Accepted Version
Download (205Kb) | Preview


    A graph $G$ is {\em triangle-saturated} if every possible edge insertion creates at least one new triangle. Furthermore, if no proper spanning subgraph has this property, then $G$ is {\em minimally triangle-saturated}. (Minimally triangle-saturated graphs of order at least 3 are the diameter 2 critical graphs.) The maximally triangle-free graphs of order $n$ are a proper subset of the minimally triangle-saturated graphs of order $n$ when $n \geq 6$. All triangle-saturated graphs are easily derivable from the minimally triangle-saturated graphs which are {\em primitive}, that is, have no duplicate vertices. We determine the 23 minimally triangle-saturated graphs of orders $n \leq 7$ and identify the 6 primitive graphs among them.

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

    Actions (login required)

    View Item