# Connectivity of Semicartesian Products

Authors: Metrose Metsidik; Helin Gong
Journal: Journal of Mathematics
 (2021)

---

## Abstract

Semicartesian product is defined on the basis of two special bipartite graphs and labeling of their vertices, and it has a pleasing property that it is composed of hexagonal structures. In this study, we give two formulae to calculate separately the connectivity and edge connectivity of a semicartesian product graph.


---

## Body

## 1. Introduction

The notion of the graph products is a central topic in the graph theory since many structural models such as physical networks, electrical circuits, roadways, and organic molecules can be viewed as the graph products of two or more graphs. Many properties of such structural models can be obtained by considering the properties of the factors of their corresponding product graphs. This not only facilities certain combinatorial optimization problems such as ordering and partitioning for parallel computing but also makes it possible to find the topological properties of the models in a much easier manner employing the topological properties of their factors, refer [1, 2] for details and examples.Hexagonal structures are everywhere, for instance, the honeycomb cells are composed of hexagons, and they are commonly believed as an example of geometric efficiency. The carbon nanotubes are the superfibers with light weight and a perfectly connected hexagonal cylindrical structure; they are also viewed as one of the most valuable objects for nanotechnology, electronics, optics, and other fields of material science and technology. Since the structures of most familiar graph products constructed by the product operation are triangles or quadrangles, it is somewhat difficult to see the hexagonal system as the product of two graphs. For this purpose, a semicartesian product graph was defined in [3], such that zigzag/armchair polyhex nanotube, polyhex nanotorus, and polyhex lattice are the semicartesian products of cycles and paths.Since connectivity measures reliability and efficiency of a graph, computing the connectivity is a fundamental problem in combinatorial optimization. The connectivity of product graphs is well studied. The authors consider the connectivity mainly in [4–6] for the Cartesian products, in [7–10] for the direct products, in [11] for the strong products, and in [12] for the lexicographic products. In almost all cases, more explicit formulae expressed in terms of corresponding graph invariants of factors are obtained; the following result is an example about Cartesian products.Theorem 1 (see [5]).
LetκG be the connectivity of a graph G and G□H, the cartesian product of two connected graphs G and H. Then,(1)κG□H=minκGVH,κHVG,δG+δH,where δG denotes the minimum degree of G.In this study, we obtain two such formulae to determine the connectivity and edge connectivity of a semicartesian product graph separately.


## 2. Preliminaries

Every graphG=VG,EG considered in this study is simple and finite. The set G′|G′≅G is called the isomorphic class of G. A subgraph S of G is induced if it contains exactly all edges with both ends in VS. The connectivity κG of a connected graph G is the fewest number of vertices whose removal from G results in a disconnected or trivial graph, and the edge connectivity λG equals the smallest cardinality of an edge subset whose removal leads to disconnection. The neighborhood of a vertex u in G is the set NGu=x∈VG|xu∈EG and the degree degGu of u in G equals the cardinality of NGu. Then, δG=mindegGu|u∈VG is the minimum degree of G. It is well-known that κG≤λG≤δG for any graph G.A bipartite graph (2-colorable graph) is a graph whose vertex set can be partitioned into two setsA and B, such that every edge connects a vertex in A to one in B, and it is symmetric if it has a symmetric drawing with respect to a straight line that passes through the middle point of each edge, or equivalently, there is a numeration of the vertices of the bipartition sets as A=a1,…,an and B=b1,…,bn, such that both the two edges aibj and ajbi appear simultaneously.An orientation of a graphG means directing every edge of G from one of its ends to the other; it is connected if there is a directed path (a sequence of vertices in which there is a directed edge pointing from each vertex in the sequence to its successor in the sequence) between any two vertices of G, and it is cycle preserving if any induced cycle of G is a directed cycle (a directed path whose first and last vertices are the same), and reversing the direction of any induced cycle does not change the isomorphic class of the oriented graph G.Definition 1 (see [3]).
LetG and H be two connected bipartite graphs with proper 2-coloring and G symmetric and H connected cycle preserving oriented. Then, the semicartesian product (semisum) of the graphs G and H, denoted by G⊔H, is defined as the follows:(2)VG⊔H=VG×VH,EG⊔H=u,vu′,v′:v=v′anduu′∈EGoru=u′andv⟶v′andu,vcolored with same color,where the symbol v⟶v′ denotes that the edge vv′ of H directed from v to v′ in the connected cycle preserving orientation of H.The vertex set and the edge set of the Cartesian productG□H of two graphs G and H are listed as follows:(3)VG□H=VG×VH,EG□H=u,vu′,v′:v=v′anduu′∈EGoru=u′andvv′∈EH.Hence, the semicartesian productG⊔H is a spanning subgraph of the corresponding Cartesian product G□H, where G is a connected symmetric bipartite graph and H is a connected cycle preserving orientable bipartite graph, and that is why we call the product graph G⊔H semicartesian product.SinceG and H are the connected bipartite graphs and G is symmetric, the vertex set of the disjoint union G∪H has a unique bipartition up to isomorphism. This implies that the semicartesian product of such two graphs is not changed under switching the colors of any factor. It is clear from the following lemma that the semicartesian product G⊔H is independent of the choice of a connected cycle preserving orientation of H.Lemma 1.
If a connected bipartite graphH is a connected cycle preserving orientable, then H has exactly two such orientations up to isomorphism.Proof.
Any induced even cycleC has a clockwise or an anticlockwise direction in a cycle preserving orientation of H. By the definition of the cycle preserving orientation, reversing the direction of C does not change the connected cycle preserving orientation of H.
So, it remains to consider the case for the paths not on a cycle. There are only two kinds of such paths inH: a path hanging on a cycle and a bridge path connecting two cycles. Since the orientation of H is connected, H contains at most two hanging paths and some bridge paths, and moreover, if the orientation of one of them is chosen, then the orientation of all others are fixed.AG-layer of a semicartesian product G⊔H is the set Gv=u,v|u∈VG, and analogously, an H-layer is Hu=u,v|v∈VH, where v∈VH and u∈VG. Notice that a subgraph of G⊔H induced by a G-layer is isomorphic to G, but a subgraph induced by an H-layer possibly consists of some stars, independent edges, and isolated vertices. If we contract each edge of the set u,viu′,vi|vi∈VH in the induced subgraph on Hu∪Hu′, then we obtain an isomorphic copy of H, where uu′∈EG.By aG-layer Gv or an H-layer Hu, we again denote the subgraph of G⊔H induced on Gv or Hu, respectively. An ambiguity could not arise since it is clear in the text whether Gv (or Hu) denotes a vertex set or a graph.In Figure1, G is a symmetric bipartite graph with black and white coloring, and H is a connected cycle preserving orientable bipartite graph. Since H has two 2-coloring and two connected cycle preserving orientations, there are four connected cycle preserving orientations together with 2-coloring of H, see graphs H1,H2,H3,H4 in Figure 1. It is easy to check that G⊔H1≅G⊔H2≅G⊔H3≅G⊔H4. Notice that black and white colors in G⊔Hi comes from G, nothing but identify H-layers of the product.Figure 1
An example of a semicartesian product.


## 3. Connectivity of Semicartesian Products

Letx be the greatest integer not bigger than x and ⌈x⌉ be the smallest integer not less than x. Then, we observe that degGu+degHv/2≤degG⊔Hu,v≤degGu+⌈degHv/2⌉ for any u,v∈VG⊔H. More precisely, if degGu1+degHv/2=degG⊔Hu1,v, then degG⊔Hu2,v=degGu2+⌈degHv/2⌉ and vice versa, where u1 is symmetric to u2 in G. So we have.Lemma 2.
LetG be a connected symmetric bipartite graph and H be a connected cycle preserving the orientable bipartite graph. Then,(4)δG⊔H=δG+δH2.Ak-set is a set consisted of k elements. A cut set, an edge cut set, or a mixed cut set of a graph is a subset of the vertex set, the edge set or the union of the vertex set, and edge set of the graph, respectively, such that its deletion creates at least one more component. A subset S′ of a cut set S is replaceable if S\S′∪ev|v∈S′ is a mixed cut set, where ev is an edge incident with v. A maximal k-replaceable set S∗ of a graph is a replaceable set of a k-cut set of the graph, such that S∗=maxS′|S′is a replaceable set of ak−cut set. Now, we are ready to state a main result of this study.Theorem 2.
LetG be a connected symmetric bipartite graph and H be a connected cycle preserving the orientable bipartite graph. Then,(5)κG⊔H=minκGVH,κHVG−S∗VG2,δG+δH2,where S∗ is a maximal κH-replaceable set of H.Proof.
Clearly,κG⊔H≤δG⊔H=δG+δH/2. Let S1 be a κG-cut set of G. Then, S1×VH is a κGVH-cut set of G⊔H. Let S2 be a κH-cut set of H with S∗⊆S2. Then, VG×S2∖S∗∪∪u∈S∗eitherA×uorB×u is a κH−S∗VG+S∗VG/2-cut set of G⊔H, where A and B are the bipartitions of VG. Thus,(6)κG⊔H≤minκGVH,κHVG−S∗VG2,δG+δH2.
In the following, we show the inverse inequality; specifically, we prove thatS≥δG+δH/2 for any cut set S of G⊔H with the following property:(7)S<minκGVH,κHVG−S∗VG2.
Notice thatGv=VG≥2δG, Hu=VH≥2δH, and Gv∩Hu=1. If both a G-layer Gv and an H-layer Hu are contained in S, then S≥2δG+δH−1 and the result follows. Hence, if S contains a G-layer, then it contains no H-layer and vice versa .Case A: there is noG-layer contained in SLetGv′:=Gv∖S and SvG:=Gv∩S, and similarly, Hu′:=Hu∖S and SuH:=Hu∩S, where v∈VH and u∈VG. Then, Gv=Gv′∪SvG and Hu=Hu′∪SuH, and Gv′≠∅ for all v∈VH. Since S<κGVH, there is h∈VH, such that Gh′ is connected.LetC1 denote the component of G⊔H−S, including Gh′ and V:=v∈VH|Gv′⊆C1. Obviously, V≠∅ since h∈V. And V≠VH; otherwise, G⊔H−S=C1 contradicts to the choice of S. Since H is connected, there are adjacent vertices v1,v2∈VH, such that v2∈VH∖V and v1∈V. Since v2∈VH∖V, we have Gv2′⊈C1. Therefore, there is an another component C2 of G⊔H−S, such that Gv2∗:=C2∩Gv2′≠∅, as shown in Figure 2. And what is more, if g,v1g,v2 is an edge with g,v2∈Gv2∗, then g,v1∈Sv1G. Hence, X:=g,v1|g,v1g,v2∈EG⊔Handg,v2∈Gv2∗⊆Sv1G.There is an edgeg,v1g,v2∈EGv2∗; otherwise, NGv2g,v2⊆Sv2G for all g,v2∈Gv2∗; therefore, Sv2G≥degGv2g,v2≥δG, and we have a desired result. Since Gv2≅G and G is bipartite, we have NGv2g1,v2∩NGv2g2,v2=∅. Obviously, NGv2g1,v2∪NGv2g2,v2⊆Sv2G∪Gv2∗. By the definition of the semicartesian product, if g1′,v1g1′,v2∉EG⊔H; then g2′,v1g2′,v2∈EG⊔H, where gi′,v2∈NGv2∗gi,v2 for i=1,2. Thus,(8)Sv1G∪Sv2G=Sv1G+Sv2G≥X+Sv2G≥NGv2∗gi,v2+NSv2Ggi,v2=degGv2gi,v2≥δGv2=δG,Wherei=1 or i=2.Suppose that there is au∈VG, such that SuH=Hu. Since SuH∩X∪Sv2G≤1 and SuH≥2δH, we have S≥Sv2G+X+SuH−1≥δG+2δH−1.Case B: there is noH-layer contained in SAlthoughHu possibly consists of some stars, independent edges, and vertices, we can also proceed analogously to Case A. Let F1 be a component of G⊔H−S, such that Hg′⊆F1 (possibly F1=C1) and let U=u∈VG|Hu′⊆F1. Since S<κHVG−S∗VG/2, there are two adjacent vertices u and u′ of G with the following property: the induced subgraph Hu′∪Hu′′ of G⊔H is connected. Thus, U≠∅. Obviously, U≠VG, and therefore, there are two adjacent vertices u1∈U and u2∈VG∖U. By a similar reason as in Case A, we obtain a set Y:=u1,h|u2,h∈Hu2∗⊆Su1H with Y+Su2H≥δH/2+1, where Hu2∗:=F2∩Hu2′ and F2 is an another component of G⊔H−S with F2∩Hu2′≠∅. If the cut set S contains a G-layer, i.e., SvG=Gv for a v∈VH, then we have again S≥SvG+Y+Su2H−1≥2δG+δH/2, since SvG≥2δG and SvG∩Y∪Su2H≤1.Case C: neither aG-layer nor an H-layer is contained in S
Obviously,X∪Sv2G∩Y∪Su2H≤2. The following three statements cannot be simultaneously true; otherwise, it is easy to drive a contradiction to the choice of S.(1)
S=Sv1G∪Sv2G∪Su1H∪Su2H=X∪Sv2G∪Y∪Su2H(2)
X∪Sv2G∩Y∪Su2H=2(3)
X∪Sv2G=δG and Y∪Su2H=δH/2+1
Hence, it follows thatS≥X∪Sv2G∪Y∪Su2H≥δG+δH/2.Figure 2
Situation from the case that noG-layer is contained in S.


## 4. Edge Connectivity of Semicartesian Products

LetV1 and V2 be two disjoint vertex subsets of a graph. We use the symbol V1,V2 for the number of edges whose one end is V1 and another is V2. In this section, we show another main result of this study.Theorem 3.
LetG be a connected symmetric bipartite graph and H be a connected cycle preserving orientable bipartite graph. Then,(9)λG⊔H=minλGVH,λHVG2,δG+δH2.Proof.
LetX be an arbitrary edge cut of G⊔H and C a component of G⊔H−X. Then, X≥VC,VG⊔H∖VC. If VC:=i≤δG+δH/2, then X≥iδG+δH/2−i−1≥δG+δH/2. So, in the following, we suppose that i>δG+δH/2.Case 1.C⊆Hu.(10)X≥i×δG>δG+δH2.Case 2.C⊆Gv.(11)X>VC,VG⊔H∖VGv≥i×δH2>δG+δH2,forδH≥2.Now, we handle the subcaseδH=1. If every vertex of C has a neighbor in other G-layer except for Gv itself, then(12)X>VC,VG⊔H∖VGv≥VC>δG+δH2.So, we suppose that there is a vertexu,v∈VC, such that NG⊔Hu,v⊆Gv. Since H is connected, there is v′∈VH, such that vv′∈EH. Then, by the definition of the semicartesian product of graphs, we have u′,vu′,v′∈EG⊔H for all u′∈NGuu. Thus,(13)X≥VC,VGv∖VC+VC,VG⊔H∖VGv≥NGv−Cu,v+NCu,v=degGvu≥δG=δG+δH2.In the following three cases, we set analogous to the proof of Theorem2 that CvG:=VC∩Gv,CuH:=VC∩Hu and Gv′:=Gv∖VC,Hu′:=Hu∖VC, where v∈VH and u∈VG.Case 3. AnH-layer is contained in C and C contains no G-layer.SinceCvG,Gv′≥λG for all v∈VH, we have(14)X≥∑v∈VHCvG,Gv′≥λGVH.Case 4. AG-layer is contained in C and C contains no H-layer.By the definition of the semicartesian product, eitheru,vu,v′∈EG⊔H or u′,vu′,v′∈EG⊔H for all vv′∈EH, where u is symmetric to u′ in G. And therefore, CuH,Hu′+Cu′H,Hu′′≥λH. Thus,(15)X≥∑u∈VGCuH,Hu′≥λHVG2.IfC contains both an H-layer and a G-layer, then there exists another component of G⊔H−X, such that it contains neither an H-layer nor a G-layer.Case 5.C contains neither a G-layer nor an H-layer, and also, C is contained neither in a G-layer nor in an H-layer.
Notice thatCvG≠∅,CuH≠∅, and Gv′≠∅,Hu′≠∅ for all u,v∈VC. We call a vertex u′,v∈NGvu,v as a G-layer neighbor of u,v and a vertex u,v′∈NHuu,v as an H-layer neighbor. In the following, we find an H-layer neighbor in Hu′′ for every u′,v∈NCvGu,v and a G-layer neighbor in Gv′′ for all u,v′∈NCuHu,v∪u,v.
If allH-layer neighbors of u′,v belong to C, then we find a substitute u′,v∗∈Cu′H for u′,v, such that an H-layer neighbor of u′,v∗ is in Hu′′. Indeed, since no H-layer is contained in C and a subgraph of G⊔H induced by Hu∪Hu′ is connected for uu′∈EG, if we fail to find a substitute u′,v∗ in Cu′H for u′,v, then, for each vertex u″,v∈NCvGu′,v, there exists a substitute u″,v∗∈Cu′′H of u″,v, such that u″,v∗ has a neighbor in Hu′′′. In this case, we consider the vertex u′,v instead of u,v.
Since the subgraph induced by aG-layer is isomorphic to G and G is connected, u,v and each of its neighbors in CuH have at least δGG-layer neighbors. Using analogous argument for u,v and its neighbors in CuH as the above, we can easily find desired substitutes u°,v∈CvG for u,v and u∗,v′∈Cv′G for u,v′, such that u°,v has a G-layer neighbor in Gv′ and u∗,v′ has a G-layer neighbor in Gv′′. Note that u′,v∗ has at least one H-layer neighbor and one G-layer neighbor in VG⊔H∖VC if u′,v∗=u∗,v′. Hence,(16)X≥VC,VG⊔H∖VC≥degGv′u,v+degCuGu,v+degHu′u,v+degCuHu,v2+1>δG+δH2,and then, it follows that(17)λG⊔H≥minλGVH,λHVG2,δG+δH2.
The proof of the inverse inequality is somewhat obvious. Since eachG-layer is isomorphic to G and there are VH disjoint G-layers in G⊔H, if we choose same λG-edge cut for each G-layer, then we get an edge cut of G⊔H with cardinality λGVH. Let S be a λH-edge cut of H and H1,H2 be the two components of H−S. Then, VG×VH1 and VG×VH2 are partitions of VG⊔H with(18)VG×VH1,VG×VH2=λHVG2.


## 5. Conclusion

In this study, we have studied the connectivity and edge connectivity of semicartesian product graphs, and we gave two formulae to calculate separately these two parameters of a semicartesian product graph.



---

*Source: 6125053-2021-10-20.xml*