2019/01/28 by Eero Räty, Eero Raty, Raty, Eero
Mathematics · #Finite Group Theory Research #Graph theory and applications #Limits and Structures in Graph Theory #math.CO
paper · pdf · doi:10.48550/arxiv.1901.09801
arxiv created 2019/01/28 · arxiv updated 2019/01/29
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 Gc to G creates an induced copy of H. Martin and Smith showed that there does not exist a P4-induced-saturated graph, where P4 is the path on 4 vertices. Axenovich and Csikós studied related questions, and asked if there exists a Pn-induced-saturated graph for any n≥5. Our aim in this short note is to show that there exists a P6-induced-saturated graph.