Efficient domination for classes of \(P_6\)-free graphs (Q2030432): Difference between revisions

In a finite undirected graph \(G\), a vertex is defined to dominate itself and all its neighbors in \(G\). This work explores the question of existence of an efficient dominating set (e.d.) for a given graph, which is a subset \(D\) of vertices such that every vertex of \(G\) is dominated by exactly one vertex of \(D\). This question is called the Efficient Domination (ED) problem. An ever-growing line of enquiry investigates the complexity of the ED problem. It is known that the ED problem is NP-complete for all graphs. More importantly, the ED problem is NP-complete even for much smaller and structured subclasses of graphs, for instance, bipartite graphs, \(2P_3\)-free chordal graphs, line graphs of bipartite graphs, planar bipartite graphs, chordal bipartite graphs, and more. The ED problem is also well-motivated by applications in coding theory and resource allocation in parallel computer networks. In this context, the main results of this work are as follows. \par i) The square of every \(P_6\)-free chordal graph having an e.d., is chordal. Further, every \((P_6,\text{house}, \text{hole}, \text{domino})\)-free graph having an e.d., is chordal. \par ii) The square of every \(P_6\)-free graph having an e.d., is hole-free. \par iii) The square of every \((P_6,\text{net})\)-free graph having an e.d., is banner-free. There are two core techniques used in the proofs of these results. The first is the more general framework of working with weighted efficient dominating sets. The second is a reduction of the ED problem to a maximum weight independent set problem on the square of the graph. An important quick consequence of the main results is that the ED problem (as well as its weighted version) can be solved in polynomial time for all the subclasses of graphs considered.