首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Induced saturation of P6
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 Gc to G creates an induced copy of H. Martin and Smith studied a related problem, and proved that there does not exist a P4-induced-saturated graph, where P4 is the path on 4 vertices. Axenovich and Csikós gave examples of families of graphs H for which H-induced-saturated graph G exists, and asked if there exists a Pn-induced-saturated graph when n5. Our aim in this short note is to show that there exists a P6-induced-saturated graph.
Keywords:05C35  Saturation  Induced subgraph
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号