2014/02/06 by Ragnar Nevries, Nevries, Ragnar, Christian Rosenke +1 · 1 citation
Computer Science · Engineering · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.2.2 #Interconnection Networks and Systems #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1402.1425
openalex publication_date 2014/02/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The class \cal Lk of k-leaf powers consists of graphs G=(V,E) that have a k-leaf root, that is, a tree T with leaf set V, where xy ∈ E, if and only if the T-distance between x and y is at most k. Structure 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 all k-leaf powers, that is, the graph class \cal L = \bigcupk=2^∞ \cal Lk, forms a proper subclass of strongly chordal graphs. Despite from that, no essential progress has been made lately. 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 arrangement \cal A(G) of a chordal graph G is a directed graph that represents the intersections between maximal cliques of G by nodes and the mutual inclusion of these vertex subsets by arcs. Recently, strongly chordal graphs have been characterized as the graphs that have a clique arrangement without bad k-cycles for k ≥ 3. We show that the clique arrangement of every graph of \cal L is free of bad 2-cycles. The question whether this characterizes the class \cal L exactly remains open.