Premium
On the edge spectrum of saturated graphs for paths and stars
Author(s) -
Balister Paul,
Dogan Ali
Publication year - 2018
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.22256
Subject(s) - combinatorics , mathematics , discrete mathematics , induced path , saturation (graph theory) , graph , pathwidth , line graph
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 P k ‐saturated graphs as well as some structural results about path‐saturated graphs that have edge counts close to the extremal number.