Induced saturation of graphs

DOI10.1016/J.DISC.2019.01.006MaRDI QIDQ1727803zbMATH OpenOpenAlexFDO

Authors Mónika Csikós, Maria Axenovich

Publication date 20 February 2019

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

saturationinduced subgraphsHamming graphs

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Connectivity (05C40) Graph operations (line graphs, products, etc.) (05C76)

Abstract: A graph $G$ is $H$-saturated for a graph $H$, if $G$ does not contain a copy of $H$ but adding any new edge to $G$ results in such a copy. An $H$-saturated graph on a given number of vertices always exists and the properties of such graphs, for example their highest density, have been studied intensively. A graph $G$ is $H$-induced-saturated if $G$ does not have an induced subgraph isomorphic to $H$, but adding an edge to $G$ from its complement or deleting an edge from $G$ results in an induced copy of $H$. It is not immediate anymore that $H$-induced-saturated graphs exist. In fact, Martin and Smith (2012) showed that there is no $P_4$-induced-saturated graph. Behrens et.al. (2016) proved that if $H$ belongs to a few simple classes of graphs such as a class of odd cycles of length at least $5$, stars of size at least $2$, or matchings of size at least $2$, then there is an $H$-induced-saturated graph. This paper addresses the existence question for $H$-induced-saturated graphs. It is shown that Cartesian products of cliques are $H$-induced-saturated graphs for $H$ in several infinite families, including large families of trees. A complete characterization of all connected graphs $H$ for which a Cartesian product of two cliques is an $H$-induced-saturated graph is given. Finally, several results on induced saturation for prime graphs and families of graphs are provided.

Recommendations

• Induced Subgraph Saturated Graphs
• Induced saturation of \(P_6\)
• On induced saturation for paths
• Graphs with induced-saturation number zero
• P_n-induced-saturated graphs exist for all n 6

Cites work

• scientific article; zbMATH DE number 3598234 (Why is no real title available?)
• scientific article; zbMATH DE number 3632548 (Why is no real title available?)
• A Note on "The Comparability Graph of a Tree"
• A Problem in Graph Theory
• A survey of minimum saturated graphs
• Characterizing subgraphs of Hamming graphs
• Complement reducible graphs
• Excluding induced subgraphs. II: Extremal graphs
• Graphs with induced-saturation number zero
• Induced saturation number

Cited in

(9)

• Induced Subgraph Saturated Graphs
• The feasible region of induced graphs
• P_n-induced-saturated graphs exist for all n 6
• Graphs with induced-saturation number zero
• Induced saturation number
• scientific article; zbMATH DE number 6949694 (Why is no real title available?)
• scientific article; zbMATH DE number 3939391 (Why is no real title available?)
• On induced saturation for paths
• Induced saturation of \(P_6\)

This page was built for publication: Induced saturation of graphs

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