A characterization of the edge connectivity of direct products of graphs

preprint2012arXivOpen access

Abstract

The direct product of graphs G=(V(G),E(G))G=(V(G),E(G)) and H=(V(H),E(H))H=(V(H),E(H)) is the graph, denoted as G×HG\times H, with vertex set V(G×H)=V(G)×V(H)V(G\times H)=V(G)\times V(H), where vertices (x1,y1)(x_1,y_1) and (x2,y2)(x_2,y_2) are adjacent in G×HG\times H if x1x2∈E(G)x_1x_2\in E(G) and y1y2∈E(H)y_1y_2\in E(H). The edge connectivity of a graph GG, denoted as λ(G)λ(G), is the size of a minimum edge-cut in GG. We introduce a function ψψ and prove the following formula %for the edge-connectivity of direct products λ(G×H)=min⁡2λ(G)∣E(H)∣,2λ(H)∣E(G)∣,δ(G×H),ψ(G,H),ψ(H,G).λ(G\times H)=\min {2λ(G)|E(H)|,2λ(H)|E(G)|,δ(G\times H), ψ(G,H), ψ(H,G)} . We also describe the structure of every minimum edge-cut in G×HG\times H.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.