The m -Component Connectivity of Leaf-Sort Graphs

Shiying Wang (), Hongmei Li and Lina Zhao
Additional contact information
Shiying Wang: School of Mathematics and Computer Science, Shanxi Normal University, Taiyuan 030031, China
Hongmei Li: School of Mathematics and Computer Science, Shanxi Normal University, Taiyuan 030031, China
Lina Zhao: School of Mathematics and Computer Science, Shanxi Normal University, Taiyuan 030031, China

Mathematics, 2024, vol. 12, issue 3, 1-16

Abstract: Connectivity plays an important role in measuring the fault tolerance of interconnection networks. As a special class of connectivity, m -component connectivity is a natural generalization of the traditional connectivity of graphs defined in terms of the minimum vertex cut. Moreover, it is a more advanced metric to assess the fault tolerance of a graph G . Let G = ( V ( G ) , E ( G ) ) be a non-complete graph. A subset F ( F ⊆ V ( G ) ) is called an m -component cut of G , if G − F is disconnected and has at least m components ( m ≥ 2 ) . The m -component connectivity of G , denoted by c κ m ( G ) , is the cardinality of the minimum m -component cut. Let C F n denote the n -dimensional leaf-sort graph. Since many structures do not exist in leaf-sort graphs, many of their properties have not been studied. In this paper, we show that c κ 3 ( C F n ) = 3 n − 6 ( n is odd) and c κ 3 ( C F n ) = 3 n − 7 ( n is even) for n ≥ 3 ; c κ 4 ( C F n ) = 9 n − 21 2 ( n is odd) and c κ 4 ( C F n ) = 9 n − 24 2 ( n is even) for n ≥ 4 .

Keywords: component connectivity; Cayley graphs; leaf-sort graph; fault tolerance (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2024
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/12/3/404/pdf (application/pdf)
https://www.mdpi.com/2227-7390/12/3/404/ (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:12:y:2024:i:3:p:404-:d:1327088

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