On the Edge Connectivity of Semi-strong Product Graphs

Qiaoling Wang; Haizhen Ren

doi:doi:10.11648/j.acm.20251406.15

Research Article |

| Peer-Reviewed

On the Edge Connectivity of Semi-strong Product Graphs

Qiaoling Wang

, Haizhen Ren^*

Published in Applied and Computational Mathematics (Volume 14, Issue 6)

Received: 9 September 2025 Accepted: 23 October 2025 Published: 11 December 2025

Views: Downloads:

Download PDF

Share This Article

Twitter
Linked In
Facebook

Abstract

The concept of edge connectivity was first proposed by K. Menger, and in communication networks and logical networks, edge connectivity can be used to measure network reliability and fault tolerance. The graph product method can be used to construct complex networks, simulate biological molecule interactions etc. At present, research on the edge connectivity of product graphs mainly focuses on the connectivity of standard product graphs, such as Cartesian product graphs, strong product graphs. The unique properties exhibited by non standard product graphs (such as semi-strong product graphs.) in practical applications are worth further exploration. The concept of semi-strong product was proposed by Mordeson and Chang Shyh, that is, for two graphs and , their semi-strong product is a graph whose vertex set is , and the edge set is defined as follows: if and are two vertices in the semi-strong product , then there is an edge between them if and only if and and are adjacent in , or and are adjacent in and and are adjacent in . And applications of the semi-strong product in fuzzy graphs, symbolic graphs, and finance have shown its broad research prospects. In this article, we mainly study the edge connectivity of semi-strong product graphs, and obtain some exact values. Furthermore, we also give an necessary and sufficient condition for a semi-strong product to be maximally edge-connected.

Published in	Applied and Computational Mathematics (Volume 14, Issue 6)
DOI	10.11648/j.acm.20251406.15
Page(s)	356-359
Creative Commons	This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited.
Copyright	Copyright © The Author(s), 2025. Published by Science Publishing Group

Keywords

Edge Connectivity, Graph Product, Semi-strong Product

1. Introduction

The concept of edge connectivity was first proposed by K. Menger in 1930s, and a systematic research was obtained by means of Menger's theorem

[1]

. Menger's theorem shows that the edge connectivity of a graph is equal to its minimum edge-cut set. This theory lays the foundation for the study of edge connectivity.

With the rapid development of information network, the reliability of network has become one of the key issues in research. Network reliability is usually measured by the connectivity of a graph, such as the edge connectivity is a key parameters to measure network reliability. For example, in communication networks and logical networks, edge connectivity can be used to measure network reliability and fault tolerance

[2-4]

. Edge connectivity is defined as the minimum number of edge deletions required to make a graph disconnected, the concept is particularly important in the design of multiprocessor networks. In addition, edge connectivity is closely related to other properties of graphs, such as diameter, minimum degree, etc. These relationships provide theoretical support for the design and optimization of complex networks.

Product graph is an important construction method in graph theory, which combines the vertices and edges of two or more graphs to generate a new graph. The graph product method can be used to construct complex networks, simulate biological molecule interactions, optimize coding algorithms, and analyze relationships in data visualization

[5-7]

. At present, research on the edge connectivity of product graphs mainly focuses on the edge connectivity of standard product graphs, such as Cartesian product graphs, strong product graphs, dictionary product graphs etc.

All graphs in this paper are finite and simple. Let

G = (V (G), E (G))

be a simple connected graph, where

V (G)

is the set of vertices of

G

and

E (G)

is the set of edges of

G

. For two graphs

G_{1} = (V (G_{1}), E (G_{1}))

and

G_{2} = (V (G_{2}), E (G_{2}))

, their Cartesian product

G_{1} ⨀ G_{2}

is a graph whose vertex set is

V (G_{1} ⨀ G_{2}) = V (G_{1}) \times V (G_{2})

, and the edge set

E (G_{1} ⨀ G_{2})

is defined as follows: if

(x_{1}, y_{1})

and

(x_{2}, y_{2})

are two vertices in the Cartesian product

G_{1} ⨀ G_{2}

, then there is an edge between them if and only if

x_{1} = x_{2}

and

y_{1}

and

y_{2}

are adjacent in

G_{2}

, or

x_{1}

and

x_{2}

are adjacent in

G_{1}

and

y_{1} = y_{2}

; their strong product

G_{1} ⊠ G_{2}

is a graph with whose vertex set is

V (G_{1} ⊠ G_{2}) = V (G_{1}) \times V (G_{2})

, and the edge set

E (G_{1} ⊠ G_{2})

is defined as follows: if

(x_{1}, y_{1})

and

(x_{2}, y_{2})

are two vertices in the strong product

G_{1} ⊠ G_{2}

, then there is an edge between them if and only if

x_{1} = x_{2}

and

y_{1}

and

y_{2}

are adjacent in

G_{2}

, or

x_{1}

and

x_{2}

are adjacent in

G_{1}

and

y_{1} = y_{2}

, or

x_{1}

and

x_{2}

are adjacent in

G_{1}

and

y_{1}

and

y_{2}

are adjacent in

G_{2}

; their lexicographic product

G_{1} ⨂ G_{2}

is a graph with whose vertex set is

V (G_{1} ⨂ G_{2}) = V (G_{1}) \times V (G_{2})

, and the edge set

E (G_{1} ⨂ G_{2})

is defined as follows: if

(x_{1}, y_{1})

and

(x_{2}, y_{2})

are two vertices in the lexicographic product

G_{1} ⨂ G_{2}

, then there is an edge between them if and only if

x_{1} = x_{2}

and

y_{1}

and

y_{2}

are adjacent in

G_{2}

, or

x_{1}

and

x_{2}

are adjacent in

G_{1}

Let

G = (V (G), E (G))

be a simple connected graph. For any vertex

v

of a graph

G

, its vertex-neighbor set is denoted by

N_{G} (v)

, which is the set of all vertices adjacent to vertex

v

in the graph

G

. The degree of

v

in the graph

G

is denoted by

d_{G} (v) = d (v)

, which refers to the number of vertices related to

v

in the graph

G

. Therefore, according to the definition of the graph, we have

d_{G} (v) = N_{G} (v)

, and the vertices in the graph

G

with degree 0 are called isolated vertices. The minimum degree of the graph

G

is denoted by

δ (G) = \min {d_{G} (v) : \forall v \in V (G)}

. If

A \subseteq G

and

A

contains all edges

uv

E (G)

that satisfy

{u, v} \in V (A)

, we say that

A

is a induced subgraph of

G

. Let

F

be a edge subset of

E (G)

, if the induced subgraph of

G - F

is not connected, then

F

is a edge-cut set of

G

. The edge connectivity of the graph

G

, denoted by

λ (G)

, is the cardinality of the minimum edge-cut set of graph

G

. For a connected graph

G

, it is said to be maximally edge-connected if and only if

λ (G) = δ (G)

. For two graphs

G_{1}

and

G_{2}

, we use

v_{i}

e_{i}

δ_{i}

λ_{i}

and

V_{i}

to denote the number of vertices, the number of edges, the minimum degree, the edge connectivity and the vertex set of

G_{i}

, respectively, where

i = 1, 2

For the edge connectivity of Cartesian product, Chiue and Shieh first gave a result in

[8]

, that is, for two connected graphs

G_{1}

and

G_{2}

, we have

λ (G_{1} ⨀ G_{2}) \geq λ (G_{1}) + λ (G_{2})

, and then there has been no good progress. Until Xu and Yang improved the result

λ (G_{1} ⨀ G_{2}) \geq λ (G_{1}) + λ (G_{2})

in the previous study

[9]

, a better result was obtained, that is, for two nontrivial graphs

G_{1}

and

G_{2}

, We have

λ (G_{1} ⨀ G_{2}) = \min {λ_{1} v_{2}, λ_{2} v_{1}, δ_{1} + δ_{2}}

, and in this article, the author use the edge-version of Menger's theorem to prove the result, then, Klavzar and Spacapan gave a proof in based on the set of minimum edge-cut

[10]

. For the edge connectivity of strong product, Researchers proved that for two connected graph

G_{1}

and

G_{2}

, we have

λ (G_{1} ⊠ G_{2}) = \min {λ_{1} (v_{2} + 2 e_{2}), λ_{2} (v_{1} + 2 e_{1}), δ_{1} + δ_{2} + δ_{1} δ_{2}}

[11, 12]

. For the edge connectivity of lexicographic product, Yang and Xu proved that for two graphs

G_{1}

and

G_{2}

, we have

λ (G_{1} ⨂ G_{2}) = \min {2 λ_{1} v_{2}^{2}, δ_{2} + δ_{1} v_{2}}

[13]

The graph product also includes some non-standard products, such as semi strong product etc. The concept of semi-strong product was proposed by Mordeson and Chang Shyh

[14]

, and its applications in fuzzy graphs, symbolic graphs, and finance have shown its broad research prospects

[8]

For two graphs

G_{1} = (V (G_{1}), E (G_{1}))

and

G_{2} = (V (G_{2}), E (G_{2}))

, their semi-strong product

G_{1} ⨁ G_{2}

is a graph whose vertex set is

V (G_{1} ⨁ G_{2}) = V (G_{1}) \times V (G_{2})

, and the edge set

E (G_{1} ⨁ G_{2})

is defined as follows: if

(x_{1}, y_{1})

and

(x_{2}, y_{2})

are two vertices in the semi-strong product

G_{1} ⨁ G_{2}

, then there is an edge between them if and only if

x_{1} = x_{2}

and

y_{1}

and

y_{2}

are adjacent in

G_{2}

, or

x_{1}

and

x_{2}

are adjacent in

G_{1}

and

y_{1}

and

y_{2}

are adjacent in

G_{2}

In this paper, we study the edge connectivity of semi-strong product graphs. Given two graphs

G_{1}

and

G_{2}

, we obtain that

λ (G_{1} ⨁ G_{2}) = \min {2 λ_{1} e_{2}, δ_{2} + δ_{1} δ_{2}}

. In further, we also give an necessary and sufficient condition for a semi-strong product to be maximally edge-connected.

2. Preliminaries

For the convenience, we define the following two types of subgraphs. For

x_{1} \in V (G_{1})

, we define

x_{1} ⨁ G_{2} = G_{2}^{x_{1}} = {(x_{1}, y_{1}) | y_{1} \in V (G_{2})}

, it is clear that the subgraph of

G_{1} ⨁ G_{2}

induced by

G_{2}^{x_{1}}

is isomorphic to

G_{2}

. Analogously, for

y_{1} \in V (G_{2})

, we define

G_{1} ⨁ y_{1} = G_{1}^{y_{1}} = {(x_{1}, y_{1}) | x_{1} \in V (G_{1})}

, but it is important to note that the subgraph of

G_{1} ⨁ G_{2}

induced by

G_{1}^{y_{1}}

is not isomorphic to

G_{1}

Lemma 2.1 (

[15]

). For any connected undirected graph

G

, we have

λ (G) \leq δ (G)

Lemma 2.2. Let

G_{1}

and

G_{2}

be two graphs, then

δ (G_{1} ⨁ G_{2}) = δ_{2} + δ_{1} δ_{2}

Proof. According to the definition of semi-strong product graph, that is, the semi-strong product

G_{1} ⨁ G_{2}

of two graphs

G_{1}

and

G_{2}

is the graph with the vertex set

V (G_{1}) \times V (G_{2})

, two vertices

(x_{1}, y_{1})

and

(x_{2}, y_{2})

being adjacent in

G_{1} ⨁ G_{2}

if and only if

x_{1} = x_{2}

and

y_{1} y_{2}

is an edge in

G_{2}

, or

x_{1} x_{2}

is an edge in

G_{1}

and

y_{1} y_{2}

is an edge in

G_{2}

, we can get the result of

δ (G_{1} ⨁ G_{2}) \geq δ_{2} + δ_{1} δ_{2}

.(1)

Assume that

δ (G_{1} ⨁ G_{2}) > δ_{2} + δ_{1} δ_{2}

,(2)

is true, that is

δ (G_{1} ⨁ G_{2}) \geq δ_{2} + δ_{1} δ_{2} + 1

.(3)

In this case, the product graph will rise to a new edge-connected relation: for two vertices

(x_{1}, y_{1})

and

(x_{2}, y_{2})

, they are adjacent in

G_{1} ⨁ G_{2}

if and only if

x_{1} = x_{2}

and

y_{1} y_{2}

is an edge in

G_{2}

, or

x_{1} x_{2}

is an edge in

G_{1}

and

y_{1} y_{2}

is an edge in

G_{2}

, or

x_{1} x_{2}

is an edge in

G_{1}

and

y_{1} = y_{2}

. At this point, three kinds of connected edges constitute a strong product graph, a contradiction. Therefore,

δ (G_{1} ⨁ G_{2}) = δ_{2} + δ_{1} δ_{2}

.(4)

3. Main Results

Theorem 3.1. Let

G_{1}

and

G_{2}

be two nontrivial graphs, and

G_{1}

is connected, then

λ (G_{1} ⨁ G_{2}) = \min {2 λ_{1} e_{2}, δ_{2} + δ_{1} δ_{2}}

Proof. Let

G = G_{1} ⨁ G_{2}

. It is clear that

λ (G) \leq δ (G) = δ_{2} + δ_{1} δ_{2}

.(5)

Let

S^{'}

be a minimum cut-set of

G_{1}

and there are two connected components

C_{1}^{'}

and

C_{2}^{'}

G_{1} - S^{'}

. Then we can see that in

G

there are exactly

2 λ_{1} e_{2}

edges between

C_{1}^{'} \times V_{2}

and

C_{2}^{'} \times V_{2}

. Hence

λ (G) \leq 2 λ_{1} e_{2}

. Then we have

λ (G_{1} ⨁ G_{2}) \leq \min {2 λ_{1} e_{2}, δ_{2} + δ_{1} δ_{2}}

.(6)

Next we only need to prove that

λ (G_{1} ⨁ G_{2}) \geq \min {2 λ_{1} e_{2}, δ_{2} + δ_{1} δ_{2}}

.(7)

Let

S

be a minimum edge-cut of

G

C_{1}

and

C_{2}

are two connected components of

G - S

. For

x \in V_{1}

, let

G_{2}^{x}

denote the subgraph of

G

induced by

x ⨁ V_{2}

It is easy to see that

G_{2}^{x}

is isomorphic to

G_{2}

. Then we define two sets, of which

X = {x \in V (G_{1}) | xy \in V (C_{1})}

for some

y \in V (G_{2})

and

Y = {x \in V (G_{1}) | xy \in V (C_{2})}

for some

y \in V (G_{2})

It is clear that

X \neq \emptyset

and

Y \neq \emptyset

. If

X \cap Y = \emptyset

, then it is easy to know that

\{X, Y\}

is a partition of

V (G_{1})

. Thus

|S| \geq \sum_{xy \in E_{G_{1}} (X, Y)} |E_{G} (V (G_{2}^{x}), V (G_{2}^{y}))|

= |E_{G_{1}} [X, Y]| 2 e_{2} = 2 λ_{1} e_{2}

.(8)

So we assume that

X \cap Y \neq \emptyset

and let

x_{0} \in X \cap Y

We need to know that for each neighbor

x

x_{0}

, the vertex-set of the graph is

V (G_{2}^{x_{0}}) \cup V (G_{2}^{x})

, and the edge-set between the vertex-sets

V (G_{2}^{x_{0}})

and

V (G_{2}^{x})

E (V (G_{2}^{x_{0}}) \cup V (G_{2}^{x}))

, denoted by

G_{2}^{[x_{0}, x]}

, has edge-connectivity

δ_{2}

Let

S_{x_{0} x} = S \cap E (V (G_{2}^{x_{0}}) \cup V (G_{2}^{x}))

, then

S_{x_{0} x} \geq δ_{2}

for each neighbor

x

x_{0}

; otherwise

G_{2}^{x_{0}} - S

is connected through

G_{2}^{x}

, which contradicts to our hypothesis.

In the following, we claim that

| S_{x_{0} x} | + | S_{x_{0}} | \geq δ_{2} + δ_{2} = 2 δ_{2}

, of which

S_{x_{0}} = S \cap E (V (G_{2}^{x_{0}}))

and

x

is a neighbor of

x_{0}

. Then let

M = V (G_{2}^{x_{0}}) \cap V (C_{1})

N = V (G_{2}^{x_{0}}) \cap V (C_{2})

, and we assume that

M \leq N

Case 1:

| M | = 1

| M | = 1

, then

| S_{x_{0} x} | + | S_{x_{0}} | \geq δ_{2} + δ_{2} = 2 δ_{2}

holds, since

S_{x_{0}} \geq δ_{2}

Case 2:

| M | \geq 2

| M | \geq 2

, we can find

| M | δ_{2}

edge-disjoint

(M, N)

-paths in

G_{2}^{x_{0}}

. Let

M = s_{1}, s_{2}, \dots, s_{u}

and

{t_{1}, t_{2}, \dots, t_{u}} \subseteq N

. Then for each

i (1 \leq i \leq u)

, there are

δ_{i}

edge-disjoint

(s_{i}, t_{i})

-paths in

G_{2}^{[x_{0}, x]}

(s_{i}, xz, t_{i})

with

z \in V (G_{2})

. So we can find

| M | δ_{2}

edge-disjoint

(M, N)

-paths.

For the sake of disconnected

M

from

N

, we must have

| S_{x_{0} x} | \geq | M | δ_{2} \geq 2 δ_{2}

and

| S_{x_{0} x} | + | S_{x_{0}} | \geq δ_{2} + δ_{2} = 2 δ_{2}

also holds.

Let

x_{1}, x_{2}, \dots, x_{δ_{1}}

δ_{1}

neighbors of

x_{0}

G_{1}

, then

|S| \geq (|S_{x_{0} x}| + |S_{x_{0}}|) + \sum_{i = 2}^{δ_{1}} |S_{x_{0}, x_{i}}|

= δ_{2} + δ_{2} + (δ_{1} - 1) δ_{2} = δ_{2} + δ_{1} δ_{2}

.(9)

This completes the proof.

Corollary 3.1. Let

G_{1}

and

G_{2}

be two connected graphs, then

G_{1} ⨁ G_{2}

is maximally edge connected if and only if

2 λ_{1} e_{2} \geq δ_{2} + δ_{1} δ_{2}

4. Conclusions

The main conclusion of this paper is as follows: for two nontrivial graphs

G_{1}

and

G_{2}

, and

G_{1}

is connected, then we have

λ (G_{1} ⨁ G_{2}) = \min {2 λ_{1} e_{2}, δ_{2} + δ_{1} δ_{2}}

. Furthermore, we obtain an necessary and sufficient condition for a semi-strong product to be maximally edge-connected.

At present, research on the edge connectivity of product graphs mainly focuses on the edge connectivity of standard product graphs, such as Cartesian product graphs, strong product graphs, lexicographic product graphs etc. The graph product also includes some non-standard products, such as semi-strong products, etc. The unique properties exhibited by non-standard product graphs (such as semi-strong product graphs, etc.) in practical applications are worth further exploration.

Author Contributions

Qiaoling Wang: Conceptualization, Resources, Software, Formal Analysis, Validation, Investigation, Visualization, Methodology, Writing – original draft

Haizhen Ren: Data curation, Supervision, Funding acquisition, Project administration, Writing – review & editing

Funding

This work was partially supported by the National Natural Science Foundation of China (Grant Nos. 12161073).

Data Availability Statement

The data supporting the outcome of this research work has been reported in this manuscript.

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	McCuaig, W. A simple proof of Menger's theorem, J. Graph Theory. 1984, 8, 427-429. HYPERLINK " https://doi.org/10.1002/jgt.3190080311" https://doi.org/10.1002/jgt.3190080311
[2]	Lai, Y. and Hua, X. Component edge connectivity and extra edge connectivity of alternating group networks, J Supercomput. 2024, 80, 313–330. HYPERLINK " https://doi.org/10.1007/s11227-0" https://doi.org/10.1007/s11227-023-05464-0
[3]	Zhang, G., Yue, Z. and Wang, D. 1-Extra 3-component edge connectivity of modified bubble-sort networks, J Supercomput. 2025, 81, 164. https://doi.org/10.1007/s11227-024-06610-y
[4]	Anastasiia, K., Bonaventura, D. M., Steffen, Z. and Volker, M. Fault Tolerance Placement in the Internet of Things, Proc. ACM Manag. 2024, 138, 1-29. HYPERLINK " https://doi.org/10.1145/365494" https://doi.org/10.1145/3654941
[5]	Xiang, Y. and Xiang, L. Controllability Gramian-based measures of graph product networks, Sci. China Inf. Sci. 2024, 67, 202207. HYPERLINK " https://doi.org/10.1007/s11432-023-4034-2" https://doi.org/10.1007/s11432-023-4034-2
[6]	Wang, S., Dong, K. and Liang, D, et al. MIPPIS: protein–protein interaction site prediction network with multi-information fusion, BMC Bioinformatics. 2024, 25, 345. HYPERLINK " https://doi.org/10.1186/s12859-024-05964-7" https://doi.org/10.1186/s12859-024-05964-7
[7]	Gao, Z., Jiang, C. and Zhang, J, et al. Hierarchical graph learning for protein–protein interaction, Nat Commun. 2023, 14, 1093. HYPERLINK " https://doi.org/10.1038/s41467-023-36736-1" https://doi.org/10.1038/s41467-023-36736-1
[8]	Chiue, W. S. and Shieh, B. S. On connectivity of the Cartesian product of two graphs, Applied Mathematics and Computation. 1999, 102(2-3), 129-137. HYPERLINK " https://doi.org/10.1016/S0096-3003" https://doi.org/10.1016/S0096-3003(98)10041-3
[9]	Xu, J. M. and Yang, C. Connectivity of Cartesian product graphs, Discrete Mathematics. 2006, 306(1), 159-165. https://doi.org/10.1016/j.disc.2005.11.010
[10]	Klavzar, S. and Spacapan, S. On the edge-connectivity of Cartesian product graphs, Asian-European Journal of Mathematics. 2008, 1(1), 93-98. HYPERLINK " https://doi.org/10.1142/S1793557108000102" https://doi.org/10.1142/S1793557108000102
[11]	Yang, C. and Xu, J. M. Connectivity and edge-connectivity of strong product graphs, J. Univ. Sci. Technol. China. 2008, 38(5), 449-455. http://staff.ustc.edu.cn/~xujm/200804.pdf
[12]	Bresar, B. and Spacapan, S. Edge-connectivity of strong products of graphs, Discus siones Mathematicae Graph Theory. 2007, 27(2): 333-343. HYPERLINK " https://doi.org/10.7151/dmgt.1365" https://doi.org/10.7151/dmgt.1365
[13]	Yang, C. and Xu, J. M. Connectivity of lexicographic product and direct product of graphs, Ars Comb. 2013, 111, 3-12. http://staff.ustc.edu.cn/~xujm/201309.pdf
[14]	Mordeson, J. N. and Chang-Shyh, P. Operations on fuzzy graphs. Information sciences. 1994, 79(3-4): 159-170. https://doi.org/10.1016/0020-0255(94)90116-3
[15]	Whitney, H. Congruent graphs and the connectivity of graphs, American Journal of Mathematics. 1932, 54(1), 150-168. https://doi.org/10.1007/978-1-4612-2972-8_4

Cite This Article

Plain Text BibTeX RIS

APA Style

Wang, Q., Ren, H. (2025). On the Edge Connectivity of Semi-strong Product Graphs. Applied and Computational Mathematics, 14(6), 356-359. https://doi.org/10.11648/j.acm.20251406.15

Copy | Download

ACS Style

Wang, Q.; Ren, H. On the Edge Connectivity of Semi-strong Product Graphs. Appl. Comput. Math. 2025, 14(6), 356-359. doi: 10.11648/j.acm.20251406.15

Copy | Download

AMA Style

Wang Q, Ren H. On the Edge Connectivity of Semi-strong Product Graphs. Appl Comput Math. 2025;14(6):356-359. doi: 10.11648/j.acm.20251406.15

Copy | Download

@article{10.11648/j.acm.20251406.15,
  author = {Qiaoling Wang and Haizhen Ren},
  title = {On the Edge Connectivity of Semi-strong Product Graphs},
  journal = {Applied and Computational Mathematics},
  volume = {14},
  number = {6},
  pages = {356-359},
  doi = {10.11648/j.acm.20251406.15},
  url = {https://doi.org/10.11648/j.acm.20251406.15},
  eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.acm.20251406.15},
  abstract = {The concept of edge connectivity was first proposed by K. Menger, and in communication networks and logical networks, edge connectivity can be used to measure network reliability and fault tolerance. The graph product method can be used to construct complex networks, simulate biological molecule interactions etc. At present, research on the edge connectivity of product graphs mainly focuses on the connectivity of standard product graphs, such as Cartesian product graphs, strong product graphs. The unique properties exhibited by non standard product graphs (such as semi-strong product graphs.) in practical applications are worth further exploration. The concept of semi-strong product was proposed by Mordeson and Chang Shyh, that is, for two graphs  and , their semi-strong product  is a graph whose vertex set is , and the edge set  is defined as follows: if  and  are two vertices in the semi-strong product , then there is an edge between them if and only if  and  and  are adjacent in , or  and  are adjacent in  and  and  are adjacent in . And applications of the semi-strong product in fuzzy graphs, symbolic graphs, and finance have shown its broad research prospects. In this article, we mainly study the edge connectivity of semi-strong product graphs, and obtain some exact values. Furthermore, we also give an necessary and sufficient condition for a semi-strong product to be maximally edge-connected.},
 year = {2025}
}

Copy | Download

TY  - JOUR
T1  - On the Edge Connectivity of Semi-strong Product Graphs
AU  - Qiaoling Wang
AU  - Haizhen Ren
Y1  - 2025/12/11
PY  - 2025
N1  - https://doi.org/10.11648/j.acm.20251406.15
DO  - 10.11648/j.acm.20251406.15
T2  - Applied and Computational Mathematics
JF  - Applied and Computational Mathematics
JO  - Applied and Computational Mathematics
SP  - 356
EP  - 359
PB  - Science Publishing Group
SN  - 2328-5613
UR  - https://doi.org/10.11648/j.acm.20251406.15
AB  - The concept of edge connectivity was first proposed by K. Menger, and in communication networks and logical networks, edge connectivity can be used to measure network reliability and fault tolerance. The graph product method can be used to construct complex networks, simulate biological molecule interactions etc. At present, research on the edge connectivity of product graphs mainly focuses on the connectivity of standard product graphs, such as Cartesian product graphs, strong product graphs. The unique properties exhibited by non standard product graphs (such as semi-strong product graphs.) in practical applications are worth further exploration. The concept of semi-strong product was proposed by Mordeson and Chang Shyh, that is, for two graphs  and , their semi-strong product  is a graph whose vertex set is , and the edge set  is defined as follows: if  and  are two vertices in the semi-strong product , then there is an edge between them if and only if  and  and  are adjacent in , or  and  are adjacent in  and  and  are adjacent in . And applications of the semi-strong product in fuzzy graphs, symbolic graphs, and finance have shown its broad research prospects. In this article, we mainly study the edge connectivity of semi-strong product graphs, and obtain some exact values. Furthermore, we also give an necessary and sufficient condition for a semi-strong product to be maximally edge-connected.
VL  - 14
IS  - 6
ER  -

Copy | Download

Author Information

Qiaoling Wang

School of Mathematics and Statistics, Qinghai Normal University, Xining, China

Contact Email

http://orcid.org/0009-0001-6058-7857
Haizhen Ren

School of Mathematics and Statistics, Qinghai Normal University, Xining, China;The State Key Laboratory of Tibetan Intelligence, Xining, China;Academy of Plateau, Science and Sustainability, Xining, China

Contact Email

http://orcid.org/0000-0001-5609-5924

Download PDF

Submit an Article

Sections

Plain Text BibTeX RIS

APA Style

Wang, Q., Ren, H. (2025). On the Edge Connectivity of Semi-strong Product Graphs. Applied and Computational Mathematics, 14(6), 356-359. https://doi.org/10.11648/j.acm.20251406.15

Copy | Download

ACS Style

Wang, Q.; Ren, H. On the Edge Connectivity of Semi-strong Product Graphs. Appl. Comput. Math. 2025, 14(6), 356-359. doi: 10.11648/j.acm.20251406.15

Copy | Download

AMA Style

Wang Q, Ren H. On the Edge Connectivity of Semi-strong Product Graphs. Appl Comput Math. 2025;14(6):356-359. doi: 10.11648/j.acm.20251406.15

Copy | Download

@article{10.11648/j.acm.20251406.15,
  author = {Qiaoling Wang and Haizhen Ren},
  title = {On the Edge Connectivity of Semi-strong Product Graphs},
  journal = {Applied and Computational Mathematics},
  volume = {14},
  number = {6},
  pages = {356-359},
  doi = {10.11648/j.acm.20251406.15},
  url = {https://doi.org/10.11648/j.acm.20251406.15},
  eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.acm.20251406.15},
  abstract = {The concept of edge connectivity was first proposed by K. Menger, and in communication networks and logical networks, edge connectivity can be used to measure network reliability and fault tolerance. The graph product method can be used to construct complex networks, simulate biological molecule interactions etc. At present, research on the edge connectivity of product graphs mainly focuses on the connectivity of standard product graphs, such as Cartesian product graphs, strong product graphs. The unique properties exhibited by non standard product graphs (such as semi-strong product graphs.) in practical applications are worth further exploration. The concept of semi-strong product was proposed by Mordeson and Chang Shyh, that is, for two graphs  and , their semi-strong product  is a graph whose vertex set is , and the edge set  is defined as follows: if  and  are two vertices in the semi-strong product , then there is an edge between them if and only if  and  and  are adjacent in , or  and  are adjacent in  and  and  are adjacent in . And applications of the semi-strong product in fuzzy graphs, symbolic graphs, and finance have shown its broad research prospects. In this article, we mainly study the edge connectivity of semi-strong product graphs, and obtain some exact values. Furthermore, we also give an necessary and sufficient condition for a semi-strong product to be maximally edge-connected.},
 year = {2025}
}

Copy | Download

TY  - JOUR
T1  - On the Edge Connectivity of Semi-strong Product Graphs
AU  - Qiaoling Wang
AU  - Haizhen Ren
Y1  - 2025/12/11
PY  - 2025
N1  - https://doi.org/10.11648/j.acm.20251406.15
DO  - 10.11648/j.acm.20251406.15
T2  - Applied and Computational Mathematics
JF  - Applied and Computational Mathematics
JO  - Applied and Computational Mathematics
SP  - 356
EP  - 359
PB  - Science Publishing Group
SN  - 2328-5613
UR  - https://doi.org/10.11648/j.acm.20251406.15
AB  - The concept of edge connectivity was first proposed by K. Menger, and in communication networks and logical networks, edge connectivity can be used to measure network reliability and fault tolerance. The graph product method can be used to construct complex networks, simulate biological molecule interactions etc. At present, research on the edge connectivity of product graphs mainly focuses on the connectivity of standard product graphs, such as Cartesian product graphs, strong product graphs. The unique properties exhibited by non standard product graphs (such as semi-strong product graphs.) in practical applications are worth further exploration. The concept of semi-strong product was proposed by Mordeson and Chang Shyh, that is, for two graphs  and , their semi-strong product  is a graph whose vertex set is , and the edge set  is defined as follows: if  and  are two vertices in the semi-strong product , then there is an edge between them if and only if  and  and  are adjacent in , or  and  are adjacent in  and  and  are adjacent in . And applications of the semi-strong product in fuzzy graphs, symbolic graphs, and finance have shown its broad research prospects. In this article, we mainly study the edge connectivity of semi-strong product graphs, and obtain some exact values. Furthermore, we also give an necessary and sufficient condition for a semi-strong product to be maximally edge-connected.
VL  - 14
IS  - 6
ER  -

Copy | Download