Connectivity, Cutsets And Hamiltonian Cycles Of Johnson Graphs

The Johnson graph J(n, k) is defined as follows: Let n and k be fixed positive integers with n≥k, andΩa fixed set of size n. Then the vertices of J(n, k) are the k-subsets ofΩ, where two such vertices are adjacent if and only if their intersection has size k -1. For a vertex v in a graph G, a local cut at v is a set of size d(v) consisting of the vertex a; or the edge vx for each x∈N(v). For a graph G, let W (?) (V(G)∪E(G)). If G - W is disconnected or a single vertex, W is defined as a generalized cutset of G; if the diameter of G - U exceeds the diameter of G, W is defined as a diameter-increasing set of G. Daven and Rodger proved that J(n, k) has connectivity k(n - k) in 1999. In this paper, firstly, we prove the same conclusion by a simpler method. Secondly, we show that every smallest generalized cut of J(n, k) is a local cut for n≠4 and k≠2; every smallest diameter-increasing set in J(n, k) is a subset of a local cut for k≠2 or n≠6 and k≠3. Finally, we obtain that J(n, k) has a Hamiltonian cycle for n≥3.