The super restricted edge-connectedness of direct product graphs

Jiaqiong Yin; Yingzhi Tian

paper

The super restricted edge-connectedness of direct product graphs

arXiv:2301.12784

Abstract

Let $G$ be a graph with vertex set $V (G)$ and edge set $E (G)$ . An edge subset $F \subseteq E (G)$ is called a restricted edge-cut if $G - F$ is disconnected and has no isolated vertices. The restricted edge-connectivity $λ^{'} (G)$ of $G$ is the cardinality of a minimum restricted edge-cut of $G$ if it has any; otherwise $λ^{'} (G) = + \infty$ . If $G$ is not a star and its order is at least four, then $λ^{'} (G) \leq ξ (G)$ , where $ξ (G) =$ min ${d_{G} (u) + d_{G} (v) - 2 : uv \in E (G)}$ . The graph $G$ is said to be maximally restricted edge-connected if $λ^{'} (G) = ξ (G)$ ; the graph $G$ is said to be super restricted edge-connected if every minimum restricted edge-cut isolates an edge from $G$ . The direct product of graphs $G_{1}$ and $G_{2}$ , denoted by $G_{1} \times G_{2}$ , is the graph with vertex set $V (G_{1} \times G_{2}) = V (G_{1}) \times V (G_{2})$ , where two vertices $(u_{1}, v_{1})$ and $(u_{2}, v_{2})$ are adjacent in $G_{1} \times G_{2}$ if and only if $u_{1} u_{2} \in E (G_{1})$ and $v_{1} v_{2} \in E (G_{2})$ . In this paper, we give a sufficient condition for $G \times K_{n}$ to be super restricted edge-connected, where $K_{n}$ is the complete graph on $n$ vertices.