2023/01/30 by Jiaqiong Yin, Yin, Jiaqiong, Yingzhi Tian +1 · 1 citation
Computer Science · Engineering · #Interconnection Networks and Systems #Advancements in Battery Materials #Advanced Graph Theory Research
paper · pdf · doi:10.48550/arxiv.2301.12784
Let G be a graph with vertex set V(G) and edge set E(G). An edge subset F⊆ 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)=+∞. If G is not a star and its order is at least four, then λ'(G)≤ ξ(G), where ξ(G)= min\dG(u) + dG(v)-2: uv ∈ 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 G1 and G2, denoted by G1× G2, is the graph with vertex set V(G1× G2) = V(G1)× V(G2), where two vertices (u1 ,v1 ) and (u2 ,v2 ) are adjacent in G1× G2 if and only if u1u2 ∈ E(G1) and v1v2 ∈ E(G2). In this paper, we give a sufficient condition for G× Kn to be super restricted edge-connected, where Kn is the complete graph on n vertices.