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


Stability of Hereditary Graph Classes Under Closure Operations
Authors:Mirka Miller  Joe Ryan  Zdeněk Ryjáček  Jakub Teska  Petr Vrána
Affiliation:1. DEPARTMENT OF MATHEMATICS, UNIVERSITY OF WEST BOHEMIA, , PILSEN, CZECH REPUBLIC;2. SCHOOL OF ELECTRICAL ENGINEERING AND COMPUTER SCIENCE, THE UNIVERSITY OF NEWCASTLE, , NEWCASTLE, AUSTRALIA;3. DEPARTMENT OF COMPUTER SCIENCE, KING'S COLLEGE, , LONDON, UK;4. DEPARTMENT OF MATHEMATICS, , ITB BANDUNG, BANDUNG, INDONESIA;5. INSTITUTE FOR THEORETICAL COMPUTER SCIENCE (ITI), CHARLES UNIVERSITY, , PILSEN, CZECH REPUBLIC
Abstract:If urn:x-wiley:03649024:media:jgt21692:jgt21692-math-0001 is a subclass of the class of claw‐free graphs, then urn:x-wiley:03649024:media:jgt21692:jgt21692-math-0002 is said to be stable if, for any urn:x-wiley:03649024:media:jgt21692:jgt21692-math-0003, the local completion of G at any vertex is also in urn:x-wiley:03649024:media:jgt21692:jgt21692-math-0004. If urn:x-wiley:03649024:media:jgt21692:jgt21692-math-0005 is a closure operation that turns a claw‐free graph into a line graph by a series of local completions and urn:x-wiley:03649024:media:jgt21692:jgt21692-math-0006 is stable, then urn:x-wiley:03649024:media:jgt21692:jgt21692-math-0007 for any urn:x-wiley:03649024:media:jgt21692:jgt21692-math-0008. In this article, we study stability of hereditary classes of claw‐free graphs defined in terms of a family of connected closed forbidden subgraphs. We characterize line graph preimages of graphs in families that yield stable classes, we identify minimal families that yield stable classes in the finite case, and we also give a general background for techniques for handling unstable classes by proving that their closure may be included into another (possibly stable) class.
Keywords:closure  stable class  forbidden subgraph
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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