Hamiltonian Connectivity, Pancyclicity And Edge Deletion Preserving The Diameter 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.A graph G is Hamiltonian-connected if there is a Hamiltonian path joining each pair of vertices in G.A graph is pancyclic if it embeds cycles of all lengths from 3 to |V(G)|.A graph is vertexpancyclic (respectively,edge-pancyclic) if every vertex(respectively,edge) is contained in cycles of all lengths from 3 to |V(G)|.In this paper,firstly, we prove that J(n,k) is Hamiltonian-connected and pancyclic,moreover,it is vertex-pancyclic and edge-pancyclic.Secondly,we give upper and lower bounds to the number un~-(J(n,k)) of edges that one can remove from J(n,k) without altering its diameter for n≥2k≥2,namely:(k-1)/(k+1)|E(J(n,k))|≤un~-(J(n,k))≤|E(J(n,k))|-|V(J(n,k))|-[(|V(J(n,k))|-1)/2k]+1. Finally,we give somc combinatorial formulas by different ways of counting |V(J(n,k))| and |E(J(n,k))|.