Super connectivity of direct product of graphs

Jin-Xin Zhou


For a graph Gκ(G) denotes its connectivity. A graph G is super connected, or simply super-κ, if every minimum separating set is the neighborhood of a vertex of G, that is, every minimum separating set isolates a vertex. The direct product G1 × G2 of two graphs G1 and G2 is a graph with vertex set V(G1 × G2) = V(G1) × V(G2) and edge set E(G1 × G2) = {(u1, v1)(u2, v2) ∣ u1u2 ∈ E(G1), v1v2 ∈ E(G2)}. Let Γ  = G × Kn, where G is a non-trivial graph and Kn(n ≥ 3) is a complete graph on n vertices. In this paper, we show that Γ  is not super-κ if and only if either κ(Γ ) = nκ(G), or Γ  ≅ Kℓ, ℓ × K3(ℓ > 0).


Super connectivity, direct product, vertex-cut.

Full Text:



ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications