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


Clique-width of graphs defined by one-vertex extensions
Authors:Michaël Rao
Institution:LIRMM - CNRS, Université Montpellier 2, 161 rue Ada, 34392 Montpellier Cedex 5, France
Abstract:Let G be a graph and u be a vertex of G. We consider the following operation: add a new vertex v such that v does not distinguish any two vertices which are not distinguished by u. We call this operation a one-vertex extension. Adding a true twin, a false twin or a pendant vertex are cases of one-vertex extensions. Here we are interested in graph classes defined by a subset of allowed one-vertex extension. Examples are trees, cographs and distance-hereditary graphs. We give a complete classification of theses classes with respect to their clique-width. We also introduce a new graph parameter called the modular-width, and we give a relation with the clique-width.
Keywords:Graph classes  Vertex extension  Cographs  Distance-hereditary graphs  Clique-width
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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