Premium
Minimum C 5 ‐saturated graphs
Author(s) -
Chen YaChen
Publication year - 2009
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.20372
Subject(s) - combinatorics , mathematics , graph , discrete mathematics
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. We prove that the minimum number of edges in a C 5 ‐saturated graph on n ≥11 vertices is sat ( n, C 5 )=⌈10( n −1)/7⌉−1 if n ∈ N 0 ={11, 12, 13, 14, 16, 18, 20} and is ⌈10( n −1)/7⌉ if n ≥11 and n ∉ N 0 . © 2009 Wiley Periodicals, Inc. J Graph Theory