Implementation of Minimum Vertex Cover in Circulant Graph having Hamiltonian path and its Application in Resource Allocation Process

Abstract

Minimum Vertex Cover is a NP Complete problem In this book chapter, we have present two theorems where the first one explain for decomposition of complete graphs K_2m+1 into circulant graph C _2m+1 (j) for m \(\geq\) 2 where j is the jump, 1 \(\le\) j \(\le\) m into m edge disjoint circulant graphs and the second theorem explain the decomposition of complete graphs K_2m+2 , C_2m+1(j) for m \(\geq\) 2 where j is the jump, 1 \(\le\)j \(\le\) m into m edge disjoint circulant graphs .An algorithm also has been developed to determine the Minimum vertex cover of circualnt edge disjoint graph K_2m+1 and K_2m+2 for m \(\geq\) 2 and finally Minimum vertex cover algorithm has been used to avoid the dead lock in process synchronization.