Characterization of graphs with orientable total domination number equal to |V|−1
In a directed graph D, a vertex subset S⊆V is a total dominating set if every vertex of D has an in-neighbor from S. A total dominating set exists if and only if every vertex has at least one in-neighbor. We call the orientation of such directed graphs valid. The total domination number of D, denote...
Elmentve itt :
| Szerzők: | |
|---|---|
| Dokumentumtípus: | Cikk |
| Megjelent: |
2025
|
| Sorozat: | DISCRETE APPLIED MATHEMATICS
378 |
| Tárgyszavak: | |
| doi: | 10.1016/j.dam.2025.07.021 |
| mtmt: | 35809811 |
| Online Access: | http://publicatio.bibl.u-szeged.hu/37496 |
| Tartalmi kivonat: | In a directed graph D, a vertex subset S⊆V is a total dominating set if every vertex of D has an in-neighbor from S. A total dominating set exists if and only if every vertex has at least one in-neighbor. We call the orientation of such directed graphs valid. The total domination number of D, denoted by γt(D), is the size of the smallest total dominating set of D. For an undirected graph G, we investigate the upper (or lower) orientable total domination number of G, denoted by DOMt(G) (or domt(G)), that is the maximum (or minimum) of the total domination numbers over all valid orientations of G. We characterize those graphs for which DOMt(G)=|V(G)|−1, and consequently we show that there exists a family of graphs for which DOMt(G) and domt(G) can be as far as possible, namely DOMt(G)=|V(G)|−1 and domt(G)=3. |
|---|---|
| Terjedelem/Fizikai jellemzők: | 234-243 |
| ISSN: | 0166-218X |