On the connectivity of Cartesian product of graphs
Jelena Govorčin, Riste Škrekovski · Ars Mathematica Contemporanea · 2013
We give a new alternative proof of Liouville’s formula which states that for any graphs G and H on at least two vertices, κ ( G □ H ) = min{ κ ( G )| H |, | G | κ ( H ), δ ( G ) + δ ( H )} , where κ and δ denote the connectivity number and minimum degree of a given graph, respectively. The main idea of our proof is based on construction of a vertex-fan which connects a vertex from V ( G □ H ) to a subgraph of G □ H . We also discuss the edge version of this problem as well as formula for products with more than two factors.