Structural Properties of Connected Domination Critical Graphs

Norah Almalki and Pawaton Kaemawichanurat
Additional contact information
Norah Almalki: Department of Mathematics and Statistics, Taif University, Taif City 26571, Saudi Arabia
Pawaton Kaemawichanurat: Mathematics and Statistics with Applications (MaSA), Department of Mathematics, Faculty of Science, King Mongkut’s University of Technology Thonburi, Bangkok 10140, Thailand

Mathematics, 2021, vol. 9, issue 20, 1-21

Abstract: A graph G is said to be k - ? c -critical if the connected domination number ? c ( G ) is equal to k and ? c ( G + u v ) < k for any pair of non-adjacent vertices u and v of G . Let ? be the number of cut vertices of G and let ? 0 be the maximum number of cut vertices that can be contained in one block. For an integer ? ? 0 , a graph G is ? -factor critical if G ? S has a perfect matching for any subset S of vertices of size ? . It was proved by Ananchuen in 2007 for k = 3 , Kaemawichanurat and Ananchuen in 2010 for k = 4 and by Kaemawichanurat and Ananchuen in 2020 for k ? 5 that every k - ? c -critical graph has at most k ? 2 cut vertices and the graphs with maximum number of cut vertices were characterized. In 2020, Kaemawichanurat and Ananchuen proved further that, for k ? 4 , every k - ? c -critical graphs satisfies the inequality ? 0 ( G ) ? min k + 2 3 , ? . In this paper, we characterize all k - ? c -critical graphs having k ? 3 cut vertices. Further, we establish realizability that, for given k ? 4 , 2 ? ? ? k ? 2 and 2 ? ? 0 ? min k + 2 3 , ? , there exists a k - ? c -critical graph with ? cut vertices having a block which contains ? 0 cut vertices. Finally, we proved that every k - ? c -critical graph of odd order with minimum degree two is 1-factor critical if and only if 1 ? k ? 2 . Further, we proved that every k - ? c -critical K 1 , 3 -free graph of even order with minimum degree three is 2-factor critical if and only if 1 ? k ? 2 .

Keywords: domination; characterization; matching; realizability (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/9/20/2568/pdf (application/pdf)
https://www.mdpi.com/2227-7390/9/20/2568/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:9:y:2021:i:20:p:2568-:d:655411

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().