## Bounds on the order of connected domination vertex critical graphs

dc.contributor.author | Kaemawichanurat, P. | |

dc.contributor.author | Caccetta, Louis | |

dc.contributor.author | Ananchuen, N. | |

dc.date.accessioned | 2019-02-19T04:16:15Z | |

dc.date.available | 2019-02-19T04:16:15Z | |

dc.date.created | 2019-02-19T03:58:21Z | |

dc.date.issued | 2018 | |

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

dc.identifier.uri | http://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.publisher | Elsevier | |

dc.title | Bounds on the order of connected domination vertex critical graphs | |

dc.type | Journal Article | |

dcterms.source.volume | 107 | |

dcterms.source.startPage | 73 | |

dcterms.source.endPage | 96 | |

dcterms.source.issn | 0835-3026 | |

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

Files | Size | Format | View |
---|---|---|---|

There are no files associated with this item. |