Skip to main content
Article
Results and Problems on Saturation Numbers for Linear Forests
Bulletin of the Institute of Combinatorics and its Applications
  • Guantao Chen, Georgia State University
  • Jill R. Faudree
  • Ralph J. Faudree, University of Memphis
  • Ronald Gould, Emory University
  • Michael S. Jacobson, University of Colorado at Denver
  • Colton Magnant, Georgia Southern University
Document Type
Article
Publication Date
1-1-2015
Disciplines
Abstract

A graph G is called H-saturated if G contains no copy of H, but for any edge e in the complement of G, the graph G + e contains some copy of H. The minimum size of an n-vertex H-saturated graph is denoted by sat(n,H) and is called the saturation number of H. In [?], Kászonyi and Tuza determined the values of sat(n,H) when H is a path or a disjoint union of edges. In this paper, we determine the values of sat(n,H) for the disjoint union of paths (a linear forest) within a constant depending only on H . Moreover, we obtain exact values for some special classes and include several conjectures.

Citation Information
Guantao Chen, Jill R. Faudree, Ralph J. Faudree, Ronald Gould, et al.. "Results and Problems on Saturation Numbers for Linear Forests" Bulletin of the Institute of Combinatorics and its Applications Vol. 75 (2015) p. 29 - 46
Available at: http://works.bepress.com/colton_magnant/59/