Implementation of Minimum Vertex Cover in Circulant Graph having Hamiltonian path and its Application in Resource Allocation Process
Atowar Ul Islam, Gautam Chakraborty, Dipankar Dutta · Book Publisher International (a part of SCIENCEDOMAIN International) · 2022
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 K2m+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 K2m+2 , C2m+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 K2m+1 and K2m+2 for m \(\geq\) 2 and finally Minimum vertex cover algorithm has been used to avoid the dead lock in process synchronization.