Premium
All minimum C 5 ‐saturated graphs
Author(s) -
Chen YaChen
Publication year - 2011
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20508
Subject(s) - combinatorics , mathematics , graph , pancyclic graph , discrete mathematics , 1 planar graph , line graph
A graph is C 5 ‐ saturated if it has no five‐cycle as a subgraph, but does contain a C 5 after the addition of any new edge. Extending our previous result, we prove that the minimum number of edges in a C 5 ‐saturated graph on n vertices is sat ( n, C 5 ) = ⌈10( n − 1)/7⌉ − 1 for 11≤ n ≤14, or n = 16, 18, 20, and is ⌈10( n − 1)/7⌉ for all other n ≥5, and we also prove that the only C 5 ‐saturated graphs with sat ( n, C 5 ) edges are the graphs described in Section 2. © 2011 Wiley Periodicals, Inc. J Graph Theory 67: 9‐26, 2011