- Tytuł:
- Matchings and total domination subdivision number in graphs with few induced 4-cycles
- Autorzy:
-
Favaron, Odile
Karami, Hossein
Khoeilar, Rana
Sheikholeslami, Seyed - Powiązania:
- https://bibliotekanauki.pl/articles/744078.pdf
- Data publikacji:
- 2010
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
matching
barrier
total domination number
total domination subdivision number - Opis:
- A set S of vertices of a graph G = (V,E) without isolated vertex is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. The total domination number γₜ(G) is the minimum cardinality of a total dominating set of G. The total domination subdivision number $sd_{γₜ(G)}$ is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the total domination number. Favaron, Karami, Khoeilar and Sheikholeslami (Journal of Combinatorial Optimization, to appear) conjectured that: For any connected graph G of order n ≥ 3, $sd_{γₜ(G)} ≤ γₜ(G)+1$. In this paper we use matchings to prove this conjecture for graphs with at most three induced 4-cycles through each vertex.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2010, 30, 4; 611-618
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki