
AbstractAn 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 T3-free chordal graphs. A T3-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.
ddc:004, Total domination, Computational Theory and Mathematics, Weighted efficient total domination, Discrete Mathematics and Combinatorics, Efficient total domination, 004, Weighted efficient total edge domination, Theoretical Computer Science, ddc: ddc:004
ddc:004, Total domination, Computational Theory and Mathematics, Weighted efficient total domination, Discrete Mathematics and Combinatorics, Efficient total domination, 004, Weighted efficient total edge domination, Theoretical Computer Science, ddc: ddc:004
| citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 9 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
