On g-Extra Connectivity of Corona-Type Graph Products.

Arati Sharma, Satyam Guragain, Ravi Srivastava · 2025

Read On g-Extra Connectivity of Corona-Type Graph Products. by Arati Sharma, Satyam Guragain, Ravi Srivastava (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-08853.txt.

Introduction

Arati Sharma, Satyam Guragain, and Ravi Srivastava compute a tougher form of connectivity for networks built by corona-style products, in a paper from 2025. Connectivity gauges how many nodes must fail before a network splits. The tougher form also demands that every leftover piece stay reasonably large.

Plain cuts can strand single nodes, which hides weak spots. The g-extra version forbids tiny fragments, so the number better matches fault tolerance in real networks. The team derives the value for several products: edge corona, neighborhood corona, two subdivision variants, and a generalized corona. Each build glues copies of one graph onto another by a fixed rule. Closed forms let designers compare builds quickly.

Catalog record

CREATORArati Sharma, Satyam Guragain, Ravi Srivastava
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE31 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-08853

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On g-Extra Connectivity of Corona-Type Graph Products. Arati Sharma, Satyam Guragain, Ravi Srivastava Abstract Connectivity is one of the central ideas in graph theory, especially when it comes to building fault-tolerant networks. A cutset S S of G G is defined to be the set of vertices in G G whose removal disconnects the graph. An R g R_{g} cutset of G G is a cutset whose removal disconnects the graph in such a way that each connected component has at least g + 1 g+1 vertices. If G G has at least one R g R_{g} cutset then the g − g- extra vertex connectivity (or the g − g- extra edge connectivity), denoted as κ g ​ ( G ) \kappa_{g}(G) ( λ g ​ ( G ) \lambda_{g}(G) ), is defined as the minimum cardinality of R g R_{g} cutset. In this paper, we obtain the g − g- extra connectivity of various corona type graph products edge corona, neighbourhood corona, subdivision vertex neighbourhood corona,subdivision edge neighbourhood corona and generalised corona product. 1 Introduction All graphs considered in this paper are connected, simple, and finite. Let G=(V,E) be a graph with vertex set V=\{v_{1},v_{2},...,v_{n}\} and edge set E(G)=\{e_{1},e_{2},...,e_{n}\} .The degree of a vertex v in a graph G , denoted as deg_{G}(v) , is the number of edges incident to v . The neighbourhood of a vertex v in a graph G , denoted by N_{G}(u) , is the set of all vertices adjacent to u . The minimum degree of graph G , denoted as \delta(G) , is the smallest degree among all v . A separating set or vertex cut of a graph G is a set S\subseteq V(G) such that G-S has more than one component. The connectivity of G , written as \kappa(G) , is the minimum size of a vertex set such that G-S is disconnected. An edge cut is a set F\subseteq E(G) such that G-F has more than one component. The edge-connectivity of G , written as \lambda(G) , is the minimum size of an edge set such that G-F is disconnected. The g- extra vertex connectivity (resp. g- extra edge connectivity) of a graph is the set S\subseteq V(G) (resp. S\subseteq E(G) whose removal disconnects the graph and each component has at least g+1 vertices, denoted as \kappa_{g}(G) (resp. \lambda_{g}(G) ). If no such set exists, we define \kappa_{g}(G)=\infty ( resp. \lambda(G)=\infty ). Define H^{i} as the copy of H corresponding to the i^{th} vertex of G . Define H_{e_{ij}} as the copy of H corresponding to edge e_{ij} . The subdivision graph of a graph G , denoted by S(G) , is the graph obtained by subdividing every edge of G exactly once, that is, for each edge e=uv\in E(G) , a new vertex is inserted into e , and the edge e is replaced by two edges (u,w) and (w,v) , where w is the newly inserted vertex. Clearly, \kappa_{0}(G)=\kappa(G) for any connected non-complete graph G . In [ 7 ] , Wang et al.in their study investigated the g -extra connectivity of various graph types. The graphs for which \kappa_{g}(G)=1 , 2 , or 3 . For trees with n vertices, they demonstrated that the g -extra connectivity is given by \kappa_{g}(T_{n})=n-2g-2 . In [ 8 ] , Wang et al. derived the precise values of g- extra connectivity of the lexicographic product, and Cartesian product, along with some applications. Zhu and Tian [ 11 ] studied g(\geq 3) extra connectivity for a strong product of G_{i} i=1,2 , where G_{i} is a maximally connected regular graph. Gu and Hao [ 3 ] deduced the 3- extra connectivity of 3- ary- n- cubes as a continuation of the work of Hsieh and Chang [ 4 ] who obtained 2- extra connectivity for k-ary-n cubes Q_{n}^{k} for k\geq 4 and n\geq 5 . Zhu et al. [ 10 ] obtained 1- extra connectivity and 2- extra connectivity for 3- ary- n- cube. Chang et al. [ 1 ] obtained 3- extra connectivity (resp. 3- extra edge connectivity) of an n-dimensional folded hypercube and provided an upper bound for g- extra connectivity on folded hypercubes for g\geq 6 . Further, Zhang and Zhou [ 9 ] extended g- extra connectivity of n- dimensional folded hypercubes for 0\leq g\leq n+1 and n\geq 7 . Whang et al. [ 6 ] explored the g- extra connectivity and g- extra diagonalisability of the crossed cube. Li et al. [ 5 ] obtained the g- extra edge connectivity for some special graphs and determined the upper and lower bounds of g- extra edge connectivity. In this paper, we explore the g- extra vertex connectivity and g- extra edge connectivity of several graph products. The rest of the paper is organized as follows. In section 3 we derive the g- extra vertex connectivity and g- extra edge connectivity of corona-type products. 2 Application and Background A multiprocessor system (MPS) comprises of an autonomous processor with local memory interconnected via communication links. When designing a multiprocessor system it is presumed that any group of components, such as processors or links, could fail at once. One of the primary considerations while designing MPS is its system level fault tolerance. Fault refers to processor or link failures ans a system is said to be fault-tolerant if it can continue to function in spite of some failure. The architecture of a MPS is typically represented by a graph G=(V,E) where V denotes the set of processors and E denotes the set of communication links connecting the processors. Two functionality criteria have been widely studied by [ 2 ] . One of these criteria for the system to be considered functional is whether the network logically retains the topological structure. This issue arises when one design is embedded within another, the presence of specific topology plays a crucial role in providing the required performance. The second criteria claims the system is functional if there is a fault-free communication path between each pair of non-faulty nodes. Hence, connectivity plays a major role when it comes to building fault-tolerant networks. 3 The g- extra vertex connectivity and g- extra edge connectivity of corona-type products We consider the base graph G as a connected,non-complete graph in all the products discussed below. 3.1 Edge corona Definition: Let G and H be two graphs such that G has n_{1} vertices and m_{1} edges, while H has n_{2} vertices and m_{2} edges. The edge corona of G and H , denoted by G\diamond H , is the graph obtained by taking one copy of G along with m_{1} separate copies of H such that each edge e_{i}=u_{i}v_{i}\in E(G) , is connected to every vertex in the i -th copy of H . Lemma 1 . [ 7 ] Let g be a non-negative integer, and let G be a connected graph. Then, \kappa_{g}(G)\leq\kappa_{g+1}(G). Lemma 2 . [ 7 ] Let g be a non-negative integer and let G be a connected graph of order n such that 0\leq g\leq\left\lfloor\frac{n-\kappa(G)-2}{2}\right\rfloor .Then, \kappa(G)\leq\kappa_{g}(G)\leq n-2g-2. Lemma 3 . [ 5 ] Let g be a non-negative integer and let G be a connected graph. Then \lambda_{g}(G)\leq\lambda_{g+1}(G). Lemma

Read the complete text