On total domination subdivision numbers of trees
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909181408182272 |
|---|---|
| author | Henning, Michael A. Topp, Jerzy |
| author_facet | Henning, Michael A. Topp, Jerzy |
| contents | A set $S$ of vertices in a graph $G$ is a total dominating set of $G$ if every vertex is adjacent to a vertex in $S$. The total domination number $γ_t(G)$ is the minimum cardinality of a total dominating set of $G$. The total domination subdivision number $\mbox{sd}_{γ_t}(G)$ of a graph $G$ is the minimum number of edges that must be subdivided (where each edge in $G$ can be subdivided at most once) in order to increase the total domination number. Haynes et al. (Discrete Math. 286 (2004) 195--202) have given a constructive characterization of trees whose total domination subdivision number is~$3$. In this paper, we give new characterizations of trees whose total domination subdivision number is 3. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_16186 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On total domination subdivision numbers of trees Henning, Michael A. Topp, Jerzy Combinatorics 05C69 A set $S$ of vertices in a graph $G$ is a total dominating set of $G$ if every vertex is adjacent to a vertex in $S$. The total domination number $γ_t(G)$ is the minimum cardinality of a total dominating set of $G$. The total domination subdivision number $\mbox{sd}_{γ_t}(G)$ of a graph $G$ is the minimum number of edges that must be subdivided (where each edge in $G$ can be subdivided at most once) in order to increase the total domination number. Haynes et al. (Discrete Math. 286 (2004) 195--202) have given a constructive characterization of trees whose total domination subdivision number is~$3$. In this paper, we give new characterizations of trees whose total domination subdivision number is 3. |
| title | On total domination subdivision numbers of trees |
| topic | Combinatorics 05C69 |
| url | https://arxiv.org/abs/2404.16186 |