Induced saturation of P₆

DOI10.1016/J.DISC.2019.111641MaRDI QIDQ2279288zbMATH OpenOpenAlexFDO

Authors Eero Räty

Publication date 12 December 2019

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

induced subgraphsaturation

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Extremal problems in graph theory (05C35)

Abstract: A graph $G$ is called $H$-induced-saturated if $G$ does not contain an induced copy of $H$, but removing any edge from $G$ creates an induced copy of $H$ and adding any edge of $G^c$ to $G$ creates an induced copy of $H$. Martin and Smith showed that there does not exist a $P_4$-induced-saturated graph, where $P_4$ is the path on 4 vertices. Axenovich and Csik'os studied related questions, and asked if there exists a $P_n$-induced-saturated graph for any $ngeq5$. Our aim in this short note is to show that there exists a $P_6$-induced-saturated graph.

Recommendations

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

Cites work

• Graphs with induced-saturation number zero
• Induced saturation number
• Induced saturation of graphs

Cited in

(6)

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

This page was built for publication: Induced saturation of \(P_6\)

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