Name
Title | ||
|---|---|---|
Perfectly relating the domination, total domination, and paired domination numbers of a graph |
Abstract | ||
|---|---|---|
The domination number γ ( G ) , the total domination number γ t ( G ) , the paired domination number γ p ( G ) , the domatic number d ( G ) , and the total domatic number d t ( G ) of a graph G without isolated vertices are related by trivial inequalities γ ( G ) ¿ γ t ( G ) ¿ γ p ( G ) ¿ 2 γ ( G ) and d t ( G ) ¿ d ( G ) . Very little is known about the graphs that satisfy one of these inequalities with equality. We study classes of graphs defined by requiring equality in one of the above inequalities for all induced subgraphs that have no isolated vertices and whose domination number is not too small. Our results are characterizations of several such classes in terms of their minimal forbidden induced subgraphs. Furthermore, we prove some hardness results, which suggest that the extremal graphs for some of the above inequalities do not have a simple structure. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1016/j.disc.2015.03.014 | Discrete Mathematics |
Keywords | Field | DocType |
domatic number,paired domination,domination,total domination,total domatic number | Discrete mathematics,Graph,Combinatorics,Vertex (geometry),Domination analysis,Mathematics,Domatic number | Journal |
Volume | Issue | ISSN |
338 | 8 | 0012-365X |
Citations | PageRank | References |
1 | 0.43 | 9 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| José D. Alvarado | 1 | 7 | 3.82 |
| Simone Dantas | 2 | 3 | 1.17 |
| Dieter Rautenbach | 3 | 3 | 0.96 |