Bounds on the order of connected domination vertex critical graphs
Abstract
© Charles Babbage Research Centre. All rights reserved. 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 fcycvertex critical if yc(G) = k and yc(Gv) < k for any vertex v of G. In this paper, we establish the order of kycvertex critical graphs in terms of k and the maximum degree A. We prove that a Jtyc.vertexcritical graph has A + k<n< (Al)(kl) + 3 vertices. Further, the upper bound is sharp for all integers k > 3 when A is even. It has been proved that every kycvertex critical graph achieving the upper bound is Aregular for k = 2 or 3. For k = 4, we prove that every 4ycvertex critical graph achieving the upper bound is Aregular. We further show that, for k = 2,3 or 4, there exists a Jtycvertex critical graph of order (Al)(fcl) + 3 if and only if A is even. We characterize, for k > 5, that every kycvertex critical graph of order A + k is isomorphic to the cycle of length k + 2.
Citation
Source Title
ISSN
School
Collection
Related items
Showing items related by title, author, creator and subject.

Ananchuen, N.; Ruangthampisan, S.; Ananchuen, W.; Caccetta, Louis (2018)© 2018, University of Queensland. All rights reserved. Let ? i (G) denote the independent domination number of G. A graph G is said to be k? i vertexcritical if ? i (G) = k and for each x ? V (G), ? i (G  x) < k. ...

Ananchuen, Watcharaphong (1993)A graph G is said to have property P(m,n,k) if for any set of m + n distinct vertices there are at least k other vertices, each of which is adjacent to the first m vertices but not adjacent to any of the latter n vertices. ...

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 ...