A Validation of the Phenomenon of Linearly Many Faults on Burnt Pancake Graphs with Its Applications

Mei-Mei Gu, Hong-Xia Yan and Jou-Ming Chang ()
Additional contact information
Mei-Mei Gu: Department of Science and Technology, China University of Political Science and Law, Beijing 102249, China
Hong-Xia Yan: Department of Science and Technology, China University of Political Science and Law, Beijing 102249, China
Jou-Ming Chang: Institute of Information and Decision Sciences, National Taipei University of Business, Taipei 10051, Taiwan

Mathematics, 2024, vol. 12, issue 2, 1-18

Abstract: “Linearly many faults” is a phenomenon observed by Cheng and Lipták in which a specific structure emerges when a graph is disconnected and often occurs in various interconnection networks. This phenomenon means that if a certain number of vertices or edges are deleted from a graph, the remaining part either stays connected or breaks into one large component along with smaller components with just a few vertices. This phenomenon can be observed in many types of graphs and has important implications for network analysis and optimization. In this paper, we first validate the phenomenon of linearly many faults for surviving graph of a burnt pancake graph B P n when removing any edge subset with a size of approximately six times λ ( B P n ) . For graph G , the ℓ -component edge connectivity denoted as λ ℓ ( G ) (resp., the ℓ -extra edge connectivity denoted as λ ( ℓ ) ( G ) ) is the cardinality of a minimum edge subset S such that G − S is disconnected and has at least ℓ components (resp., each component of G − S has at least ℓ + 1 vertices). Both λ ℓ ( G ) and e λ ( ℓ ) ( G ) are essential metrics for network reliability assessment. Specifically, from the property of “linearly many faults”, we may further prove that λ 5 ( B P n ) = λ ( 3 ) ( B P n ) + 3 = 4 n − 3 for n ⩾ 5 ; λ 6 ( B P n ) = λ ( 4 ) ( B P n ) + 4 = 5 n − 4 and λ 7 ( B P n ) = λ ( 5 ) ( B P n ) + 5 = 6 n − 5 for n ⩾ 6 .

Keywords: burnt pancake graph; component edge connectivity; extra edge connectivity; linearly many faults; conditional connectivity (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/2/268/pdf (application/pdf)
https://www.mdpi.com/2227-7390/12/2/268/ (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:2:p:268-:d:1318893

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