Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

On the total domination subdivision numbers in graphs

100%

Sheikholeslami S.

Open Mathematics

2010

tom 8

nr 3

468-473

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 γ t(G) is the minimum cardinality of a total dominating set of G. The total domination subdivision number sdγt (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. Karami, Khoeilar, Sheikholeslami and Khodkar, (Graphs and Combinatorics, 2009, 25, 727–733) proved that for any connected graph G of order n ≥ 3, sdγ t(G) ≤ 2γ t(G) − 1 and posed the following problem: Characterize the graphs that achieve the aforementioned upper bound. In this paper we first prove that sdγ t(G) ≤ 2α′(G) for every connected graph G of order n ≥ 3 and δ(G) ≥ 2 where α′(G) is the maximum number of edges in a matching in G and then we characterize all connected graphs G with sdγ t(G)=2γt(G)−1.

Ograniczanie wyników

1 Open Mathematics

1 Sheikholeslami S.

1 2010

Wyniki wyszukiwania

On the total domination subdivision numbers in graphs