Currently displaying 1 – 3 of 3

Showing per page

Order by Relevance | Title | Year of publication

Restrained domination in unicyclic graphs

Johannes H. HattinghErnst J. JoubertMarc LoizeauxAndrew R. PlummerLucas van der Merwe — 2009

Discussiones Mathematicae Graph Theory

Let G = (V,E) be a graph. A set S ⊆ V is a restrained dominating set if every vertex in V-S is adjacent to a vertex in S and to a vertex in V-S. The restrained domination number of G, denoted by γ r ( G ) , is the minimum cardinality of a restrained dominating set of G. A unicyclic graph is a connected graph that contains precisely one cycle. We show that if U is a unicyclic graph of order n, then γ r ( U ) n / 3 , and provide a characterization of graphs achieving this bound.

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)