Proof of a conjecture on connectivity of Kronecker product of graphs |
| |
Authors: | Yun Wang Baoyindureng Wu |
| |
Affiliation: | aCollege of Mathematics and System Science, Xinjiang University, Urumqi, Xinjiang 830046, PR China |
| |
Abstract: | For a graph G, κ(G) denotes its connectivity. The Kronecker product G1×G2 of graphs G1 and G2 is the graph with the vertex set V(G1)×V(G2), two vertices (u1,v1) and (u2,v2) being adjacent in G1×G2 if and only if u1u2∈E(G1) and v1v2∈E(G2). Guji and Vumar [R. Guji, E. Vumar, A note on the connectivity of Kronecker products of graphs, Appl. Math. Lett. 22 (2009) 1360–1363] conjectured that for any nontrivial graph G, κ(G×Kn)=min{nκ(G),(n−1)δ(G)} when n≥3. In this note, we confirm this conjecture to be true. |
| |
Keywords: | Kronecker product Cartesian product Connectivity |
本文献已被 ScienceDirect 等数据库收录! |
|