Bounds on the order of connected domination vertex critical graphs
|dc.identifier.citation||Kaemawichanurat, P. and Caccetta, L. and Ananchuen, N. 2018. Bounds on the order of connected domination vertex critical graphs. Journal of Combinatorial Mathematics and Combinatorial Computing. 107: pp. 73-96.|
A vertex subset D of G is a dominating set of G if every vertex in V(G)-D is adjacent to a vertex in D. Moreover, a dominating set D of G is a connected dominating set if G[D] is connected. The minimum cardinality of a connected dominating set of G is called the connected domination number of G and is denoted by yc(G). A graph G is said to be fc-yc-vertex critical if yc(G) = k and yc(G-v) < k for any vertex v of G. In this paper, we establish the order of k-yc-vertex critical graphs in terms of k and the maximum degree A. We prove that a Jt-yc.-vertexcritical graph has A + k<n< (A-l)(k-l) + 3 vertices. Further, the upper bound is sharp for all integers k > 3 when A is even. It has been proved that every k-yc-vertex critical graph achieving the upper bound is A-regular for k = 2 or 3. For k = 4, we prove that every 4-yc-vertex critical graph achieving the upper bound is A-regular. We further show that, for k = 2,3 or 4, there exists a Jt-yc-vertex critical graph of order (A-l)(fc-l) + 3 if and only if A is even. We characterize, for k > 5, that every k-yc-vertex critical graph of order A + k is isomorphic to the cycle of length k + 2.
|dc.title||Bounds on the order of connected domination vertex critical graphs|
|dcterms.source.title||Journal of Combinatorial Mathematics and Combinatorial Computing|
|curtin.department||School of Electrical Engineering, Computing and Mathematical Science (EECMS)|
|curtin.accessStatus||Fulltext not available|
Files in this item
There are no files associated with this item.