language-icon Old Web
English
Sign In

Induced saturation of P6

2019 
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 studied a related problem, and proved that there does not exist a P 4 -induced-saturated graph, where P 4 is the path on 4 vertices. Axenovich and Csikos gave examples of families of graphs H for which H -induced-saturated graph G exists, and asked if there exists a P n -induced-saturated graph when n ≥ 5 . Our aim in this short note is to show that there exists a P 6 -induced-saturated graph.
    • Correction
    • Source
    • Cite
    • Save
    • Machine Reading By IdeaReader
    4
    References
    3
    Citations
    NaN
    KQI
    []