The gg-extra connectivity of the strong product of paths and cycles

preprint2022arXivOpen access

Abstract

Let GG be a connected graph and gg be a non-negative integer. The gg-extra connectivity of GG is the minimum cardinality of a set of vertices in GG, if it exists, whose removal disconnects GG and leaves every component with more than gg vertices. The strong product G1⊠G2G_1 \boxtimes G_2 of graphs G1=(V1,E1)G_1=(V_{1}, E_{1}) and G2=(V2,E2)G_2=(V_{2}, E_{2}) is the graph with vertex set V(G1⊠G2)=V1×V2V(G_1 \boxtimes G_2)=V_{1} \times V_{2}, where two distinct vertices (x1,x2),(y1,y2)∈V1×V2(x_{1}, x_{2}), (y_{1}, y_{2}) \in V_{1} \times V_{2} are adjacent in G1⊠G2G_1 \boxtimes G_2 if and only if xi=yix_{i}=y_{i} or xiyi∈Eix_{i} y_{i} \in E_{i} for i=1,2i=1, 2. In this paper, we obtain the gg-extra connectivity of the strong product of two paths, the strong product of a path and a cycle, and the strong product of two cycles.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.