Paper Info
Title
On weighted efficient total domination
Abstract
An efficiently total dominating set of a graph G is a subset of its vertices such that each vertex of G is adjacent to exactly one vertex of the subset. If there is such a subset, then G is an efficiently total dominable graph (G is etd). In this paper, we prove NP-completeness of the etd decision problem on the class of planar bipartite graphs of maximum degree 3. Furthermore, we give an efficient decision algorithm for T"3-free chordal graphs. A T"3-free graph is a graph that does not contain as induced subgraph a claw, every edge of which is subdivided exactly twice. In the main part, we present three graph classes on which the weighted etd problem is polynomially solvable: claw-free graphs, odd-sun-free chordal graphs (including strongly chordal graphs) and graphs which only induce cycles of length divisible by four (including chordal bipartite graphs). In addition, claw-free etd graphs are shown to be perfect.
Year
DOI
Venue
2012
10.1016/j.jda.2011.06.001
J. Discrete Algorithms
Keywords
Field
DocType
odd-sun-free chordal graph,efficient total domination,total domination,planar bipartite graph,weighted efficient total domination,3-free chordal graph,claw-free etd graph,graph class,graph g,chordal graph,claw-free graph,chordal bipartite graph,weighted efficient total edge domination,3-free graph
Discrete mathematics,Combinatorics,Outerplanar graph,Indifference graph,Interval graph,Chordal graph,Cograph,Pathwidth,Mathematics,Split graph,Maximal independent set
Journal
Volume
ISSN
Citations 
10,
Journal of Discrete Algorithms
3
PageRank 
References 
Authors
0.42
11
1
Name
Order
Citations
PageRank
Oliver Schaudt19521.74