Graph cover-saturation

DOI10.1007/S00373-019-02071-WMaRDI QIDQ2334084zbMATH OpenOpenAlexFDO

Authors Danny Rorabaugh

Publication date 6 November 2019

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1801.04250

zbMATH Keywords

graph coveragegraph saturationsaturation number

Mathematics Subject Classification ID

Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

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.

Recommendations

• Few \(H\) copies in \(F\)-saturated graphs
• Results and problems on saturation numbers for linear forests
• scientific article; zbMATH DE number 6686834
• Saturation spectrum of paths and stars
• A lower bound on the saturation number, and graphs for which it is sharp

Cites work

• A Problem in Graph Theory
• A survey of minimum saturated graphs
• Asymptotic growth of sparse saturated structures is locally determined
• Asymptotic results on saturated graphs
• Cycle-saturated graphs with minimum number of edges
• Exact bounds for some hypergraph saturation problems
• scientific article; zbMATH DE number 4081590 (Why is no real title available?)
• scientific article; zbMATH DE number 140096 (Why is no real title available?)
• scientific article; zbMATH DE number 2192110 (Why is no real title available?)
• scientific article; zbMATH DE number 3275275 (Why is no real title available?)
• scientific article; zbMATH DE number 3050594 (Why is no real title available?)
• On the structure of linear graphs
• Saturated graphs with minimal number of edges
• Saturation in random graphs
• The Game Saturation Number of a Graph

Cited in

(1)

• scientific article; zbMATH DE number 3939391 (Why is no real title available?)

This page was built for publication: Graph cover-saturation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2334084)