The 3-restricted edge-connectivity of the direct product graphs
Discrete Applied Mathematics · 2026-09 · 390 · 62-71
DOI: 10.1016/j.dam.2026.04.003 ↗Kurz gefasst
Fachartikel in der Zeitschrift Discrete Applied Mathematics, 2026-09. Verfasst von Wenxin Wang und 1 weiteren Autor:innen. Die Arbeit nennt 12 Literaturangaben. Gefördert von: Xinjiang Uygur Autonomous Region Natural Science Foundation, National Natural Science Foundation of China.
Abstract (Originalsprache)
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 \( \lambda_3(G) \), is defined as the minimum cardinality among all 3-restricted edge-cuts if there are at least one; otherwise, \( \lambda_3(G) = +\infty \). It is proved that $\lambda_3(G)\leq\xi_3(G)$ if $G$ has a 3-restricted edge-cut, where $\xi_3(G) = \min \left\{ |[X, V(G) \setminus X]_G|:|X| = 3 \text{ and } G[X] \text{ is connected} \right\}.$ If \( \lambda_3(G) = \xi_3(G) \), then \( G \) is said to be maximally 3-restricted edge-connected. The direct product of two graphs $G$ and $H$, denoted by $G \times H$, is defined as the graph with vertex set \( V(G \times H) = V(G) \times V(H) \), where two vertices \( (u_1, v_1) \) and \( (u_2, v_2) \) are adjacent in \( G \times H \) if and only if \( u_1u_2 \in E(G) \) and \( v_1v_2 \in E(H) \). In this paper, we determine, for a regular connected graph \( G\), the 3-restricted edge-connectivity of \( G \times C_n \), \( G \times K_n \) and \( G \times T_n \), where \( C_n \), \( K_n \) and \( T_n \) are the cycle, the complete graph and the total graph with \( n \) vertices, respectively. As corollaries, we establish sufficient conditions for the direct product graphs \( G \times C_n \), \( G \times K_n \) and \( G \times T_n \) to be maximally 3-restricted edge-connected.
Förderung
- Xinjiang Uygur Autonomous Region Natural Science Foundation
- National Natural Science Foundation of China
Zitieren
APA
Wang, W., & Tian, Y. (2026). The 3-restricted edge-connectivity of the direct product graphs. Discrete Applied Mathematics, 390, 62-71. https://doi.org/10.1016/j.dam.2026.04.003
Vancouver
Wang W, Tian Y. The 3-restricted edge-connectivity of the direct product graphs. Discrete Applied Mathematics. 2026;390:62-71. doi:10.1016/j.dam.2026.04.003
BibTeX
@article{Wang2026,
author = {Wang, Wenxin and Tian, Yingzhi},
title = {The 3-restricted edge-connectivity of the direct product graphs},
journal = {Discrete Applied Mathematics},
year = {2026},
volume = {390},
pages = {62--71},
doi = {10.1016/j.dam.2026.04.003}
}
EUVIMED