Currently displaying 1 – 2 of 2

Showing per page

Order by Relevance | Title | Year of publication

Total domination edge critical graphs with maximum diameter

Lucas C. van der MerweCristine M. MynhardtTeresa W. Haynes — 2001

Discussiones Mathematicae Graph Theory

Denote the total domination number of a graph G by γₜ(G). A graph G is said to be total domination edge critical, or simply γₜ-critical, if γₜ(G+e) < γₜ(G) for each edge e ∈ E(G̅). For 3ₜ-critical graphs G, that is, γₜ-critical graphs with γₜ(G) = 3, the diameter of G is either 2 or 3. We characterise the 3ₜ-critical graphs G with diam G = 3.

Domination Subdivision Numbers

A set S of vertices of a graph G = (V,E) is a dominating set if every vertex of V-S is adjacent to some vertex in S. The domination number γ(G) is the minimum cardinality of a dominating set of G, and the domination subdivision number s d γ ( 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 domination number. Arumugam conjectured that 1 s d γ ( G ) 3 for any graph G. We give a counterexample to this conjecture. On the other hand, we show...

Page 1

Download Results (CSV)