Back to Search
Start Over
On the edge spectrum of saturated graphs for paths and stars.
- Source :
-
Journal of Graph Theory . Dec2018, Vol. 89 Issue 4, p364-385. 22p. - Publication Year :
- 2018
-
Abstract
- For a given graph H, we say that a graph G on n vertices is H‐saturated if H is not a subgraph of G, but for any edge e∈E(G¯) the graph G+e contains a subgraph isomorphic to H. The set of all values m for which there exists an H‐saturated graph on n vertices and m edges is called the edge spectrum for H‐saturated graphs. In the present article, we study the edge spectrum for H‐saturated graphs when H is a path or a star. In particular, we show that the edge spectrum for star‐saturated graphs consists of all integers between the saturation number and extremal number, and the edge spectrum of path‐saturated graphs includes all integers from the saturation number to slightly below the extremal number, but in general will include gaps just below the extremal number. We also investigate the second largest Pk‐saturated graphs as well as some structural results about path‐saturated graphs that have edge counts close to the extremal number. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 03649024
- Volume :
- 89
- Issue :
- 4
- Database :
- Academic Search Index
- Journal :
- Journal of Graph Theory
- Publication Type :
- Academic Journal
- Accession number :
- 132481890
- Full Text :
- https://doi.org/10.1002/jgt.22256