Graphs with induced-saturation number zero

Abstract: Given graphs

G

and

H

,

G

is

H

-saturated if

H

is not a subgraph of

G

, but for all

e o t i n E (G)

,

H

appears as a subgraph of

G + e

. While for every

n g e | 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

n g e | V (H) |

for which every

n

-vertex graph

G

either contains

H

as an induced subgraph, or there exists

e o t i n E (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.

Review text

Summary: Given graphs \(G\) and \(H\), \(G\) is \(H\)-saturated if \(H\) is not a subgraph of \(G\), but for all \(e \notin E(G)\), \(H\) appears as a subgraph of \(G + e\). While for every \(n \geqslant |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 \(n \geqslant |V(H)|\), for which every \(n\)-vertex graph \(G\) either contains \(H\) as an induced subgraph, or there exists \(e \notin E(G)\) such that \(G + e\) does not contain \(H\) as an induced subgraph. To circumvent this Martin and Smith make use of a generalized notion of ``graph 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. This yields graphs that are \(H\)-induced-saturated. That is, graphs such that no induced copy of \(H\) exists, but adding or deleting any edge creates an induced copy of \(H\). We introduce a new parameter for such graphs, indsat\(^\ast\)(\(n,H\)), which is the minimum number of edges in an \(H\)-induced-saturated graph. We provide bounds on indsat\(^\ast\)(\(n,H\)) for many graphs. In particular, we determine indsat\(^\ast\)(\(n,H\)) completely when \(H\) is the paw graph \(K_{1,3}+e\), and we determine indsat\(^\ast\)(\(n,K_{1,3}\)) within an additive constant of four.

Recommendations

Cites work

Cited in

(7)

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)