کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419001 | 681731 | 2015 | 14 صفحه PDF | دانلود رایگان |
In this paper, we present the clique arrangement A(G)A(G) for a chordal graph GG to describe the intersections between the maximal cliques of GG more precisely than in clique trees or related concepts. In particular, the node set of A(G)A(G) contains a node X=C1∩C2∩⋯X=C1∩C2∩⋯ for every set C1,C2,…C1,C2,… of maximal cliques of GG. In A(G)A(G), there is an arc from a node XX to a node ZZ, if XX is a subset of ZZ and there is no node YY, that is a superset of XX and a subset of ZZ.As clique arrangements may have exponential size, we analyze this notion for strongly chordal graphs GG. We provide a new characterization of strongly chordal graphs in terms of forbidden cyclic structures in the corresponding clique arrangements and we show how to compute the clique arrangement of a strongly chordal graph efficiently.
Journal: Discrete Applied Mathematics - Volume 181, 30 January 2015, Pages 221–234