research-article

Induced saturation of graphs

Authors:

Maria Axenovich,

Mónika CsikósAuthors Info & Claims

Volume 342, Issue 4

Pages 1195 - 1212

https://doi.org/10.1016/j.disc.2019.01.006

Published: 01 April 2019 Publication History

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.

References

[1]

Behrens S., Erbes C., Santana M., Yager D., Yeager E., Graphs with induced-saturation number zero, Electron. J. Combin. 23 (1) (2016) Paper 1.54, 23.

Google Scholar

[2]

Chvátal V., Hammer P.L., Aggregation of inequalities in integer programming, Ann. Discrete Math. 1 (1977) 145–162.

Crossref

Google Scholar

[3]

Corneil D.G., Lerchs H., Stewart Burlingham L., Complement reducible graphs, Discrete Appl. Math. 3 (3) (1981) 163–174.

Google Scholar

[4]

Erdős P., Hajnal A., Moon J.W., A problem in graph theory, Amer. Math. Monthly 71 (1964) 1107–1110.

Google Scholar

[5]

Faudree J.R., Faudree R.J., Schmitt J.R., A survey of minimum saturated graphs, Electron. J. Combin. (2011) Dynamic survey 19.

Google Scholar

[6]

S. Földes, P.L. Hammer, Split graphs, in: Proceedings of the 8th South-Eastern Conference on Combinatorics Graph Theory and Computing, 1977, pp. 311–315.

Google Scholar

[7]

Klavžar S., Peterin I., Characterizing subgraphs of Hamming graphs, J. Graph Theory 4 (49) (2005) 302–312.

Google Scholar

[8]

W. Mantel, Problem 28, solution by H. Gouwentak, W. Mantel, J. Teixeira de Mattes, F. Schuh, W.A. Wytho, Wiskundige Opgaven, pp. 60–61.

Google Scholar

[9]

Martin R.R., Smith J.J., Induced saturation number, Discrete Math. 312 (21) (2012) 3096–3106.

Google Scholar

[10]

Prömel H.J., Steger A., Excluding induced subgraphs. ii. Extremal graphs, Discrete Appl. Math. 44 (1–3) (1993) 283–294.

Google Scholar

[11]

Turán P., On an extremal problem in graph theory, Mat. Fiz. Lapok 48 (1941) 436–452. (in Hungarian).

Google Scholar

[12]

Wolk E.S., A note on “The comparability graph of a tree”, Proc. Amer. Math. Soc. 16 (1965) 17–20.

Google Scholar

Index Terms

Induced saturation of graphs
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph algorithms
      2. Graph enumeration

Index terms have been assigned to the content through auto-classification.

Recommendations

Forbidden Induced Subgraphs of Double-split Graphs

In the course of proving the strong perfect graph theorem, Chudnovsky, Robertson, Seymour, and Thomas showed that every perfect graph either belongs to one of five basic classes or admits one of several decompositions. Four of the basic classes are ...
Characterizing subgraphs of Hamming graphs

Cartesian products of complete graphs are known as Hamming graphs. Using embeddings into Cartesian products of quotient graphs we characterize subgraphs, induced subgraphs, and isometric subgraphs of Hamming graphs. For instance, a graph G is an induced ...
Minimal induced subgraphs of the class of 2-connected non-Hamiltonian wheel-free graphs
Abstract
Given a graph G and a graph property P we say that G is minimal with respect to P if no proper induced subgraph of G has the property P. An HC-obstruction is a minimal 2-connected non-Hamiltonian graph. Given a graph H, a graph G is H-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Discrete Mathematics Volume 342, Issue 4

Apr 2019

297 pages

ISSN:0012-365X

Issue’s Table of Contents

Elsevier B.V.

Publisher

Elsevier Science Publishers B. V.

Netherlands

Publication History

Published: 01 April 2019

Author Tags

Qualifiers

Research-article

Index Terms

Recommendations

Forbidden Induced Subgraphs of Double-split Graphs

Characterizing subgraphs of Hamming graphs

Minimal induced subgraphs of the class of 2-connected non-Hamiltonian wheel-free graphs

Comments

Published In

Publisher

Publication History

Author Tags

Qualifiers

Other Metrics

Article Metrics

Other Metrics

Abstract

References

Index Terms

Recommendations

Forbidden Induced Subgraphs of Double-split Graphs

Characterizing subgraphs of Hamming graphs

Minimal induced subgraphs of the class of 2-connected non-Hamiltonian wheel-free graphs

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

View options

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations