Generalized Connectivity of the Mycielskian Graph under g -Extra Restriction

Jinyu Zou, He Li (), Shumin Zhang and Chengfu Ye
Additional contact information
Jinyu Zou: School of Mathematics and Physics, Qinghai University, Xining 810016, China
He Li: School of Information Engineering, Communication University of Shanxi, Jinzhong 030619, China
Shumin Zhang: School of Mathematics and Statistics, Qinghai Normal University, Xining 810001, China
Chengfu Ye: School of Mathematics and Statistics, Qinghai Normal University, Xining 810001, China

Mathematics, 2023, vol. 11, issue 19, 1-11

Abstract: The g -extra connectivity is a very important index to evaluate the fault tolerance, reliability of interconnection networks. Let g be a non-negative integer, G be a connected graph with vertex set V and edge set E , a subset S ⊆ V is called a g -extra cut of G if the graph induced by the set G − S is disconnected and each component of G − S has at least g + 1 vertices. The g-extra connectivity of G , denoted as κ g ( G ) , is the cardinality of the minimum g -extra cut of G . Mycielski introduced a graph transformation to discover chromatic numbers of triangle-free graphs that can be arbitrarily large. This transformation converts a graph G into a new compound graph called μ ( G ) , also known as the Mycielskian graph of G . In this paper, we study the relationship on g -extra connectivity between the Mycielskian graph μ ( G ) and the graph G . In addition, we show that κ 3 ( μ ( G ) ) = 2 κ 1 ( G ) + 1 for κ 1 ( G ) ≤ m i n { 4 , ⌊ n 2 ⌋ } , and prove the bounds of κ 2 g + 1 ( μ ( G ) ) for g ≥ 2 .

Keywords: connectivity; g -extra connectivity; Mycielskian graph (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2023
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/11/19/4043/pdf (application/pdf)
https://www.mdpi.com/2227-7390/11/19/4043/ (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:11:y:2023:i:19:p:4043-:d:1246407

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