Name
Abstract | ||
|---|---|---|
Graph $G$ is $F$-saturated if $G$ contains no copy of graph $F$ but any edge added to $G$ produces at least one copy of $F$. One common variant of saturation is to remove the former restriction: $G$ is $F$-semi-saturated if any edge added to $G$ produces at least one new copy of $F$. In this paper we take this idea one step further. Rather than just allowing edges of $G$ to be in a copy of $F$, we require it: $G$ is $F$-covered if every edge of $G$ is in a copy of $F$. It turns out that there is smooth interaction between coverage and semi-saturation, which opens for investigation a natural analogue to saturation numbers. Therefore we present preliminary cover-saturation theory and structural bounds for the cover-saturation numbers of graphs. We also establish asymptotic cover-saturation densities for cliques and paths, and upper and lower bounds (with small gaps) for cycles and stars. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1007/s00373-019-02071-w | Graphs and Combinatorics |
DocType | Volume | Issue |
Journal | 35 | 5 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Danny Rorabaugh | 1 | 1 | 1.18 |