Towards a Characterization of Leaf Powers by Clique Arrangements
Towards a Characterization of Leaf Powers by Clique Arrangements
复制标题
DOI：
10.1007/s00373-016-1707-x
复制
发表时间：
2014-02
影响因子：
0.7
通讯作者：
Ragnar Nevries;Christian Rosenke
中科院分区：
文献类型：
--
作者：
Ragnar Nevries;Christian Rosenke
在本文中，我们使用团排列的新概念来表明叶幂是强弦图的自然特例。弦图G的团排列是一个有向图，它通过节点表示G的最大团之间的交集，并通过弧表示这些顶点子集的包含关系。最近，强弦图被描述为具有团排列而没有坏循环的图。 k 叶幂类由具有 ak 叶根的图组成，即具有叶集 V 的树 T，其中当且仅当 x 和 y 之间的 T 距离最大为 k。已经发现了 2、3、4 和（在某种程度上）5 叶幂的结构特征和线性时间识别算法，并且已知所有叶幂的并集（即图类）形成强弦图的真子类。尽管如此，最近没有取得任何实质性进展。在本文中，我们描述了强弦图的子类，该子类具有派系排列，没有某些不良的 2 环，并表明它包含在该类中。
In this paper, we use the new notion of clique arrangements to suggest that leaf powers are a natural special case of strongly chordal graphs. The clique arrangementof a chordal graphGis a directed graph that represents the intersections between maximal cliques ofGby nodes and the inclusion relation of these vertex subsets by arcs. Recently, strongly chordal graphs have been characterized as the graphs that have a clique arrangement without badk-cycles for. The classofk-leaf powers consists of graphsthat have ak-leaf root, that is, a treeTwith leaf setV, whereif and only if theT-distance betweenxandyis at mostk. Structural characterizations and linear time recognition algorithms have been found for 2-, 3-, 4-, and, to some extent, 5-leaf powers, and it is known that the union of allk-leaf powers, that is, the graph class, forms a proper subclass of strongly chordal graphs. Despite that, no essential progress has been made lately. In this paper, we characterize the subclass of strongly chordal graphs that have a clique arrangement without certain bad 2-cycles and show thatis contained in that class.