کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
420258 | 683913 | 2011 | 12 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Equistable graphs, general partition graphs, triangle graphs, and graph products Equistable graphs, general partition graphs, triangle graphs, and graph products](/preview/png/420258.png)
In this paper we examine the connections between equistable graphs, general partition graphs and triangle graphs. While every general partition graph is equistable and every equistable graph is a triangle graph, not every triangle graph is equistable, and a conjecture due to Jim Orlin states that every equistable graph is a general partition graph. The conjecture holds within the class of chordal graphs; if true in general, it would provide a combinatorial characterization of equistable graphs.Exploiting the combinatorial features of triangle graphs and general partition graphs, we verify Orlin’s conjecture for several graph classes, including AT-free graphs and various product graphs. More specifically, we obtain a complete characterization of the equistable graphs that are non-prime with respect to the Cartesian or the tensor product, and provide some necessary and sufficient conditions for the equistability of strong, lexicographic and deleted lexicographic products. We also show that the general partition graphs are not closed under the strong product, answering a question by McAvaney et al.
Journal: Discrete Applied Mathematics - Volume 159, Issue 11, 6 July 2011, Pages 1148–1159