Show simple item record

dc.contributor.authorKaemawichanurat, P.
dc.contributor.authorCaccetta, Louis
dc.contributor.authorAnanchuen, N.
dc.date.accessioned2019-02-19T04:16:15Z
dc.date.available2019-02-19T04:16:15Z
dc.date.created2019-02-19T03:58:21Z
dc.date.issued2018
dc.identifier.citationKaemawichanurat, 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.
dc.identifier.urihttp://hdl.handle.net/20.500.11937/74215
dc.description.abstract

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.publisherElsevier
dc.titleBounds on the order of connected domination vertex critical graphs
dc.typeJournal Article
dcterms.source.volume107
dcterms.source.startPage73
dcterms.source.endPage96
dcterms.source.issn0835-3026
dcterms.source.titleJournal of Combinatorial Mathematics and Combinatorial Computing
curtin.departmentSchool of Electrical Engineering, Computing and Mathematical Science (EECMS)
curtin.accessStatusFulltext not available


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record