کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
437608 | 690164 | 2015 | 11 صفحه PDF | دانلود رایگان |
The square of a graph G , denoted G2G2, is obtained from G by putting an edge between two distinct vertices whenever their distance is two. Then G is called a square root of G2G2. Deciding whether a given graph has a square root is known to be NP-complete, even if the root is required to be a chordal graph or even a split graph.We present a polynomial time algorithm that decides whether a given graph has a Ptolemaic square root. If such a root exists, our algorithm computes one with a minimum number of edges.In the second part of our paper, we give a characterization of the graphs that admit a 3-sun-free split square root. This characterization yields a polynomial time algorithm to decide whether a given graph has such a root, and if so, to compute one.
Journal: Theoretical Computer Science - Volume 602, 18 October 2015, Pages 39–49