
arXiv: 1803.06244
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.
30 pages, 12 figures
ddc:510, Connectivity, saturation, Graph operations (line graphs, products, etc.), induced subgraphs, [INFO] Computer Science [cs], 05C35, 05C75, 05C76, 510, Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.), FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Mathematics, info:eu-repo/classification/ddc/510, Hamming graphs
ddc:510, Connectivity, saturation, Graph operations (line graphs, products, etc.), induced subgraphs, [INFO] Computer Science [cs], 05C35, 05C75, 05C76, 510, Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.), FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Mathematics, info:eu-repo/classification/ddc/510, Hamming graphs
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 4 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
