Minimally triangle-saturated graphs: adjoining a single vertex | NOVA. The University of Newcastle's Digital Repository

Home

Description	Size	Format
Publisher version (open access)	158 KB	Adobe Acrobat PDF	View/Open

Please use this identifier to cite or link to this item: http://hdl.handle.net/1959.13/27157

Title: Minimally triangle-saturated graphs: adjoining a single vertex
Author/Creator: Eggleton, Roger B.; MacDougall, James A.
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.
Relation: Australasian Journal of Combinatorics Vol. 25, p. 263-278
Relation: http://ajc.maths.uq.edu.au/volume_contents.php3?vol=25
Date: 2002
Publisher: Centre for Discrete Mathematics & Computing
Keyword(s): triangle-saturated graphs; primitive minimally saturated extensions; triangle-free graphs; vertex addition
Resource Type: journal article
Identifier: http://hdl.handle.net/1959.13/27157
Identifier: ISSN:1034-4942

30 Visitors

51 Hits

NOVA. The University of Newcastle's Digital Repository