The 3-restricted Edge-Connectivity of Strong Product Graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914469505925120 |
|---|---|
| author | Wang, Wenxin Tian, Yingzhi Wang, Jing |
| author_facet | Wang, Wenxin Tian, Yingzhi Wang, Jing |
| contents | An edge subset \( S \subseteq E(G) \) is called a 3-restricted edge-cut if $G-S$ is disconnected and each component of \( G - S \) contains at least three vertices. The 3-restricted edge-connectivity of a graph \( G \), denoted by \( λ_3(G) \), is defined as the minimum cardinality among all 3-restricted edge-cuts if there are at least one; otherwise, \( λ_3(G) = +\infty \). It is proved that $λ_3(G)\leqξ_3(G)$ if $G$ has a 3-restricted edge-cut, where $ξ_3(G) = \min \{ |[X, V(G) \setminus X]_G||X \subseteq V(G),|X| = 3 \text{ and } G[X] \text{ is connected}\}.$ If \( λ_3(G) = ξ_3(G) \), then \( G \) is said to be maximally 3-restricted edge-connected. The strong product of graphs \( G \) and \( H \), denoted by \( G \boxtimes H \), is the graph with the vertex set $ V(G)\times V(H) $ and the edge set $ \{(x_{1},y_{1})(x_{2},y_{2})|x_{1}=x_{2}\text{ and }y_{1}y_{2}\in E(H);\text{ or }y_{1}=y_{2} $ and $ x_{1}x_{2}\in E(G) $; or $ x_{1}x_{2}\in E(G) $ and $ y_{1}y_{2}\in E(H)\}$. In this paper, we prove that \( G \boxtimes C_{n} \) is maximally 3-restricted edge-connected, and determine the 3-restricted edge-connectivity of \( G \boxtimes K_{n} \), where \( G \) is a maximally edge-connected graph, \( C_{n} \) and \( K_{n} \) are the cycle and the complete graph of order \( n \), respectively. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_11644 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The 3-restricted Edge-Connectivity of Strong Product Graphs Wang, Wenxin Tian, Yingzhi Wang, Jing Combinatorics An edge subset \( S \subseteq E(G) \) is called a 3-restricted edge-cut if $G-S$ is disconnected and each component of \( G - S \) contains at least three vertices. The 3-restricted edge-connectivity of a graph \( G \), denoted by \( λ_3(G) \), is defined as the minimum cardinality among all 3-restricted edge-cuts if there are at least one; otherwise, \( λ_3(G) = +\infty \). It is proved that $λ_3(G)\leqξ_3(G)$ if $G$ has a 3-restricted edge-cut, where $ξ_3(G) = \min \{ |[X, V(G) \setminus X]_G||X \subseteq V(G),|X| = 3 \text{ and } G[X] \text{ is connected}\}.$ If \( λ_3(G) = ξ_3(G) \), then \( G \) is said to be maximally 3-restricted edge-connected. The strong product of graphs \( G \) and \( H \), denoted by \( G \boxtimes H \), is the graph with the vertex set $ V(G)\times V(H) $ and the edge set $ \{(x_{1},y_{1})(x_{2},y_{2})|x_{1}=x_{2}\text{ and }y_{1}y_{2}\in E(H);\text{ or }y_{1}=y_{2} $ and $ x_{1}x_{2}\in E(G) $; or $ x_{1}x_{2}\in E(G) $ and $ y_{1}y_{2}\in E(H)\}$. In this paper, we prove that \( G \boxtimes C_{n} \) is maximally 3-restricted edge-connected, and determine the 3-restricted edge-connectivity of \( G \boxtimes K_{n} \), where \( G \) is a maximally edge-connected graph, \( C_{n} \) and \( K_{n} \) are the cycle and the complete graph of order \( n \), respectively. |
| title | The 3-restricted Edge-Connectivity of Strong Product Graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2604.11644 |