Minimum Vertex Cover of Circulant Graph having Hamiltonian Path and its Application
Atowar Ul Islam, Jayanta Choudhury, Bichitra Kalita · Indian Journal of Science and Technology · 2016
Objective: The Minimum Vertex Cover of a circulant graph for m≥2 obtained from the complete graph K2m+1 and K2m+2 have been discussed. Methods: Minimum Vertex Cover is a NP Complete problem. Various properties to find out the Minimum Vertex Cover of different types of circulant graphs of even and odd values of m≥2 have been studied. Findings: After studied the Minimum vertex cover we find two theorems for the graph K2m+1 and K2m+2 and results are also observed. An algorithm also developed to find the Minimum Vertex Cover. Application: An application of minimum vertex cover has been cited to avoid the deadlock condition in process graph with an example.Keywords: Circulant Graph, Complete Graph, Deadlock, Minimum Vertex Cover, Process, Resources