A vertex set D in a finite undirected graph G is an efficient dominating set (e.d.s 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.s. in G, is known to be NP-complete even for very restricted graph classes such as for 2P3-free chordal graphs while it is solvable in polynomial time for P6-free chordal graphs (and even for P6-free graphs). A standard reduction from the NP-complete Exact Cover problem shows that ED is NP-complete for a very special subclass of chordal graphs generalizing split graphs. The reduction implies that ED is NP-complete e.g. for double-gem-free chordal graphs while it is solvable in linear time for gem-free chordal graphs (by various reasons such as bounded clique-width, distance-hereditary graphs, chordal square etc.), and ED is NP-complete for butterfly-free chordal graphs while it is solvable in linear time for 2P2-free graphs. We show that (weighted) ED can be solved in polynomial time for H-free chordal graphs when H is net, extended gem, or S1,2,3.

On efficient domination for some classes of H-free chordal graphs

Mosca R.
2020-01-01

Abstract

A vertex set D in a finite undirected graph G is an efficient dominating set (e.d.s 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.s. in G, is known to be NP-complete even for very restricted graph classes such as for 2P3-free chordal graphs while it is solvable in polynomial time for P6-free chordal graphs (and even for P6-free graphs). A standard reduction from the NP-complete Exact Cover problem shows that ED is NP-complete for a very special subclass of chordal graphs generalizing split graphs. The reduction implies that ED is NP-complete e.g. for double-gem-free chordal graphs while it is solvable in linear time for gem-free chordal graphs (by various reasons such as bounded clique-width, distance-hereditary graphs, chordal square etc.), and ED is NP-complete for butterfly-free chordal graphs while it is solvable in linear time for 2P2-free graphs. We show that (weighted) ED can be solved in polynomial time for H-free chordal graphs when H is net, extended gem, or S1,2,3.
File in questo prodotto:
File Dimensione Formato  
1-s2.0-S0166218X19302495-main.pdf

Solo gestori archivio

Descrizione: Article
Tipologia: PDF editoriale
Dimensione 534.45 kB
Formato Adobe PDF
534.45 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11564/760355
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 0
social impact