Extra connectivity of networks modeled by the strong product graphs

Qinze Zhu and Yingzhi Tian

Applied Mathematics and Computation, 2024, vol. 477, issue C

Abstract: Given a non-negative integer g, the g-extraconnectivity in a connected graph G is defined as the minimum number of vertices that, when removed, results in G becoming disconnected and each remaining component containing more than g vertices. As an extension of the connectivity, the g-extraconnectivity provides a better measurement for the fault tolerance of an interconnection network. The strong product G1⊠G2 of graphs G1 and G2 is the graph with vertex set V(G1)×V(G2), where two distinct vertices (a1,b1) and (a2,b2) are adjacent if and only if a1=a2 and b1b2∈E(G2), or b1=b2 and a1a2∈E(G1), or a1a2∈E(G1) and b1b2∈E(G2). In this paper, we focus on networks modeled by the strongproductG1⊠G2. We determine the g(≤3)-extraconnectivity of G1⊠G2, where G1 and G2 are regular and maximally connected graphs with girth at least g+4. Additionally, we give the g(≤3)-extra conditional diagnosability of G1⊠G2 under PMC model.

Keywords: Strong product; Extra connectivity; PMC model; Extra conditional diagnosability (search for similar items in EconPapers)
Date: 2024
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300324002868
Full text for ScienceDirect subscribers only

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:eee:apmaco:v:477:y:2024:i:c:s0096300324002868

DOI: 10.1016/j.amc.2024.128825

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().