pith. sign in

arxiv: 1208.4995 · v1 · pith:WOT6BZHZnew · submitted 2012-08-24 · 🧮 math.CO

A characterization of the edge connectivity of direct products of graphs

classification 🧮 math.CO
keywords timeslambdadirectconnectivitydenotededgeedge-cutgraph
0
0 comments X
read the original abstract

The direct product of graphs $G=(V(G),E(G))$ and $H=(V(H),E(H))$ is the graph, denoted as $G\times H$, with vertex set $V(G\times H)=V(G)\times V(H)$, where vertices $(x_1,y_1)$ and $(x_2,y_2)$ are adjacent in $G\times H$ if $x_1x_2\in E(G)$ and $y_1y_2\in E(H)$. The edge connectivity of a graph $G$, denoted as $\lambda(G)$, is the size of a minimum edge-cut in $G$. We introduce a function $\psi$ and prove the following formula %for the edge-connectivity of direct products $$\lambda (G\times H)=\min {2\lambda(G)|E(H)|,2\lambda(H)|E(G)|,\delta(G\times H), \psi(G,H), \psi(H,G)} .$$ We also describe the structure of every minimum edge-cut in $G\times H$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.