Critical graphs with respect to total domination and connected domination
Access Status
Authors
Date
2016Type
Metadata
Show full item recordAbstract
A graph G is said to be kγt critical if the total domination number γt(G)= k and γt (G + uv) < k for every uv /∈ E(G). A kγccritical graph G is a graph with the connected domination number γc(G) = k and γc(G + uv) < k for every uv /∈ E(G). Further, a ktvc graph is a graph with γt(G) = k and γt (G − v) < k for all v ∈ V(G), where v is not a support vertex (i.e. all neighbors of v have degree greater than one). A 2connected graph G is said to be kcvc if γc(G) = k and γc (G − v) < k for all v ∈ V(G). In this paper, we prove that connected kγt critical graphs and kγccritical graphs are the same if and only if 3 ≤ k ≤ 4. For k ≥ 5, we concentrate on the class of connected kγtcritical graphs G with γc (G) = k and the class of kγccritical graphs G with γt(G) = k. We show that these classes intersect but they do not need to be the same. Further, we prove that 2connected ktvc graphs and kcvc graphs are the same if and only if 3 ≤ k ≤ 4. Similarly, for k ≥ 5, we focus on the class of 2connected ktvc graphs G with γc (G) = k and the class of 2connected kcvc graphs G with γt (G) = k. We finish this paper by showing that these classes do not need to be the same.
Citation
Source Title
Department
Collections
Related items
Showing items related by title, author, creator and subject.

Ananchuen, Watcharaphong; Ananchuen, Nawarat; Caccetta, Louis (2010)Let γ c (G) denote the minimum cardinality of a connected dominating set for G. A graph G is kγ c critical if γ c (G) = k, but γ c (G + xy) < k for xy Î E([`(G)])xyE(G) . Further, for integer r ≥ 2, G is said to be k(γ ...

Lam, Bee K. (1999)A network is a system that involves movement or flow of some commodities such as goods and services. In fact any structure that is in the form of a system of components some of which interact can be considered as a network. ...

Ananchuen, Nawarat (1994)Let G be a simple connected graph on 2n vertices with a perfect matching. For 1 ≤ k ≤ n  1, G is said to be kextendable if for every matching M of size k in G there is a perfect matching in G containing all the edges ...