Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
New Polynomial Case for Efficient Domination in P 6-free Graphs
verfasst von : T. Karthick
Erschienen in: Algorithms and Discrete Applied Mathematics
Verlag: Springer International Publishing
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
In a graph
G
, an
efficient dominating set
is a subset
D
of vertices such that
D
is an independent set and each vertex outside
D
has exactly one neighbor in
D
. The
Efficient Dominating Set
problem (EDS) asks for the existence of an efficient dominating set in a given graph
G
, and the
Weighted Efficient Dominating Set
problem (WEDS) asks for an efficient dominating set of minimum total weight in the given graph
G
with vertex weight function
w
on
V
(
G
). The (W)EDS is known to be
NP
-complete for
P
7
-free graphs, and is known to be polynomial time solvable for
P
5
-free graphs. However, the computational complexity of the (W)EDS problem is unknown for
P
6
-free graphs. In this paper, we show that the WEDS problem can be solved in polynomial time for a subclass of
P
6
-free graphs, namely (
P
6
, banner)-free graphs, where 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.