- Title
- Minimally triangle-saturated graphs: adjoining a single vertex
- Creator
- Eggleton, Roger B.; MacDougall, James A.
- Relation
- Australasian Journal of Combinatorics Vol. 25, p. 263-278
- Relation
- http://ajc.maths.uq.edu.au/volume_contents.php3?vol=25
- Publisher
- Centre for Discrete Mathematics & Computing
- Resource Type
- journal article
- Date
- 2002
- Description
- 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 primitive (no two vertices have the same neighbourhood). The results are applied to construct primitive maximal triangle-free graphs of every order n ≥ 9.
- Subject
- triangle-saturated graphs; primitive minimally saturated extensions; triangle-free graphs; vertex addition
- Identifier
- uon:1417
- Identifier
- http://hdl.handle.net/1959.13/27157
- Identifier
- ISSN:1034-4942
- Full Text
- Reviewed
- Hits: 2743
- Visitors: 2878
- Downloads: 164
| Thumbnail | File | Description | Size | Format | |||
|---|---|---|---|---|---|---|---|
| View Details Download | ATTACHMENT01 | Publisher version (open access) | 158 KB | Adobe Acrobat PDF | View Details Download |