English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Let G be a finite undirected graph. A vertex dominates itself and all its neighbors in G. A vertex set D is an efficient dominating sete.d. for short of G if every vertex of G is dominated by exactly one vertex of D. The Efficient Domination ED problem, which asks for the existence of an e.d. in G, is known to be $$\mathbb {NP}$$-complete even for very restricted graph classes such as $$P_7$$-free chordal graphs. The ED problem on a graph G can be reduced to the Maximum Weight Independent Set MWIS problem on the square of G. The complexity of the ED problem is an open question for $$P_6$$-free graphs and was open even for the subclass of $$P_6$$-free chordal graphs. In this paper, we show that squares of $$P_6$$-free chordal graphs that have an e.d. are chordal; this even holds for the larger class of $$P_6$$, house, hole, domino-free graphs. This implies that ED/WeightedED is solvable in polynomial time for $$P_6$$, house, hole, domino-free graphs; in particular, for $$P_6$$-free chordal graphs. Moreover, based on our result that squares of $$P_6$$-free graphs that have an e.d. are hole-free and some properties concerning odd antiholes, we show that squares of $$P_6$$, house-free graphs $$P_6$$, bull-free graphs, respectively that have an e.d. are perfect. This implies that ED/WeightedED is solvable in polynomial time for $$P_6$$, house-free graphs and for $$P_6$$, bull-free graphs the time bound for $$P_6$$, house, hole, domino-free graphs is better than that for $$P_6$$, house-free graphs. The complexity of the ED problem for $$P_6$$-free graphs remains an open question.

Efficient Domination for Some Subclasses of $$P_6$$ -free Graphs in Polynomial Time