Hamiltonian graphs 34 For which values of n r and s are the

3.4 For which values of n, r and s are the graphs in Exercise 3.1 Hamiltonian? For which values are they semi-Hamiltonian? (a) the complete graph Kn; (b) the complete bipartite graph Kr,s; (c) the n-cube On

Solution

The third part is not clear, i am answering the first two parts condition for being hamiltonian or not in detail. Thanks,Nikhil

a) The number of ways of choosing the initial vertex or reference vertext in the graph

Reference vertex has N different possibilities

second vertex will be having (N-1) different possibilities

...........................

similarly (N-1)th vertex will be having 2 possibilities

Total Number of Possibilities = N * (N-1) * (N-2) *....*1

in the hamiltonian circuit we don\'t caer about the reference vertex hence number of hamiltonians will be equal to

Possibilities = (N-1) * (N-2) *....*1 = (N-1)!

Hence, for number of possibilities equal to (N-1)! the graph will be a hamiltonian graph

b) Given the complete bi-partite graph Km.n such that we split the graph as given below

------ Seperate the r vertices on the left

-------Selected group of s vertices on the right

If (r=s) then we can construct the hamiltonian cycle but if r is not equal to s, then there won\'t be any hamiltonian cycle possible.

Assuming a case where r < s, all edges of left connected with the vertices on the right => we will exhaust all the vertices of left hand side and we need to visit one vertex more than one, hence this is a contradiction

=> implies graph will be hamiltonian when value of r=s

c) On is hamiltonian for every value greater than 2

Since O2 is a cycle of 4 => it is hamiltonian, now join one vertex and proceed as above in similar way