کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
420260 | 683913 | 2011 | 10 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Recognizing Helly Edge-Path-Tree graphs and their clique graphs Recognizing Helly Edge-Path-Tree graphs and their clique graphs](/preview/png/420260.png)
We present a unifying procedure for recognizing intersection graphs of Helly families of paths in a tree and their clique graphs. The Helly property makes it possible to look at these recognition problems as variants of the Graph Realization Problem, namely, the problem of recognizing Edge-Path-Tree matrices. Our result heavily relies on the notion of pie introduced in [M.C. Golumbic, R.E. Jamison, The edge intersection graphs of paths in a tree, Journal of Combinatorial Theory, Series B 38 (1985) 8–22] and on the observation that Helly Edge-Path-Tree matrices form a self-dual class of Helly matrices. Coupled to the notion of reduction presented in the paper, these facts are also exploited to reprove and slightly refine some known results for Edge-Path-Tree graphs.
Journal: Discrete Applied Mathematics - Volume 159, Issue 11, 6 July 2011, Pages 1166–1175