Indian Journal of Science and Technology

Open Access Open Access  Restricted Access Subscription Access

Minimum Vertex Cover of Circulant Graph having Hamiltonian Path and its Application


Affiliations
1 Department of Computer Science and IT, Cotton College, Guwahati - 781001, Assam, India
2 Department of Mathematics, Swadeshi College of Commerce, Guwahati - 781013, Assam, India
3 Department of Computer Application (MCA), Assam Engineering College, Guwahati - 781013, Assam, India
 

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.
User

Abstract Views: 205

PDF Views: 0




  • Minimum Vertex Cover of Circulant Graph having Hamiltonian Path and its Application

Abstract Views: 205  |  PDF Views: 0

Authors

Atowar-ul Islam
Department of Computer Science and IT, Cotton College, Guwahati - 781001, Assam, India
Jayanta Kr Choudhury
Department of Mathematics, Swadeshi College of Commerce, Guwahati - 781013, Assam, India
Bichitra Kalita
Department of Computer Application (MCA), Assam Engineering College, Guwahati - 781013, Assam, India

Abstract


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.



DOI: https://doi.org/10.17485/ijst%2F2016%2Fv9i37%2F127085