Structure of squares and efficient domination in graph classes

详细信息    查看全文

• 作者：T. Karthick ^{karthick@isichennai.res.in" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Graph algorithms ; Square graph ; Domination ; Efficient domination ; Graph classes
• 刊名：Theoretical Computer Science
• 出版年：2016
• 出版时间：1 November 2016
• 年：2016
• 卷：652
• 期：Complete
• 页码：38-46
• 全文大小：363 K

文摘

For any two vertices u and v in a graph G  , d_G(u,v)$d_G(u,v)$ denote the distance between u and v in G. The square   of a graph G=(V,E)$G=(V,E)$ is the graph G²=(V,E²)$G^2=(V,E^2)$ such that uv∈E²$uv\in E^2$ if and only if d_G(u,v)∈{1,2}$d_G(u,v)\in \{1,2\}$. An efficient dominating set (e.d. for short) in G is a subset D of vertices such that D is an independent set and each vertex outside D has exactly one neighbor in D  . In general, (i) if P$\mathcal{P}$ is a (hereditary) graph property, and if a graph G   satisfies P$\mathcal{P}$, then G²$G^2$ does not need to satisfy P$\mathcal{P}$, and (ii) if H is any graph, and if G is a H  -free graph that has an e.d., then G²$G^2$ need not be H-free.

In this paper, we show that the squares of (P₆$P_6$, banner)-free graphs that have an e.d. are again (P₆$P_6$, banner)-free. This result together with some known results implies that the Efficient Dominating Set problem (which asks for the existence of an e.d. in a given graph G  ) can be solved in time 13c9913dc" title="Click to view the MathML source">O(n³)$O(n^3)$ for (P₆$P_6$, banner)-free graphs. Here, P_t$P_t$ denotes the chordless path on t vertices, and a banner is the graph obtained from a chordless cycle on four vertices by adding a vertex that has exactly one neighbor on the cycle.