Graphs with induced-saturation number zero

MaRDI QIDQ276201zbMATH OpenFDO

Authors Sarah Behrens, Catherine Erbes, Michael Santana, Derrek Yager, Elyse Yeager

Publication date 3 May 2016

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1503.02105, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p54

zbMATH Keywords

induced subgraphgraph saturation

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Structural characterization of families of graphs (05C75)

Abstract: Given graphs $G$ and $H$, $G$ is $H$-saturated if $H$ is not a subgraph of $G$, but for all $eotinE(G)$, $H$ appears as a subgraph of $G+e$. While for every $nge|V(H)|$, there exists an $n$-vertex graph that is $H$-saturated, the same does not hold for induced subgraphs. That is, there exist graphs $H$ and values of $nge|V(H)|$ for which every $n$-vertex graph $G$ either contains $H$ as an induced subgraph, or there exists $eotinE(G)$ such that $G+e$ does not contain $H$ as an induced subgraph. To circumvent this, Martin and Smith make use of trigraphs when introducing the concept of induced saturation and the induced saturation number of graphs. This allows for edges that can be included or excluded when searching for an induced copy of H, and the induced saturation number is the minimum number of such edges that are required. In this paper, we show that the induced saturation number of many common graphs is zero. Consequently, this yields graphs, instead of trigraphs, that are H-induced-saturated. We introduce a new parameter for such graphs, indsat*(n;H), which is the minimum number of edges in an H-induced-saturated graph on n vertices. We provide bounds on indsat*(n;H) for many graphs. In particular, we determine indsat*(n;paw) completely, and indsat*(n;$K_{1,3}$) for infinitely many n.

Recommendations

• Induced Subgraph Saturated Graphs
• Induced saturation of graphs
• Induced saturation of \(P_6\)
• On induced saturation for paths
• Induced saturation number

Cites work

• scientific article; zbMATH DE number 3598234 (Why is no real title available?)
• A Problem in Graph Theory
• A survey of minimum saturated graphs
• Blow-up lemma
• Characterizations of derived graphs
• Induced saturation number
• Representation of a finite graph by a set of intervals on the real line
• Saturated graphs with minimal number of edges
• The Comparability Graph of a Tree
• The strong perfect graph theorem
• The structure of claw-free graphs
• Trivially perfect graphs

Cited in

(6)

• On induced saturation for paths
• Induced saturation of graphs
• Induced saturation of \(P_6\)
• Induced Subgraph Saturated Graphs
• Graphs with no induced house nor induced hole have the de Bruijn–Erdös property
• \(P_n\)-induced-saturated graphs exist for all \(n \geqslant 6\)

This page was built for publication: Graphs with induced-saturation number zero

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