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

Atowar ul Islam; Jayanta Kr Choudhury   and Bichitra Kalita

doi:10.17485/ijst/2016/v9i37/98001

Article

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

VIEWS 938
PDF 647

Abstract
Full-Text HTML
Full-Text PDF
How to Cite

Indian Journal of Science and Technology

DOI: 10.17485/ijst/2016/v9i37/98001

Year: 2016, Volume: 9, Issue: 37, Pages: 1-7

Original Article

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

Atowar-ul Islam^1*, Jayanta Kr Choudhury² and Bichitra Kalita³

¹ Department of Computer Science and IT, Cotton College, Guwahati - 781001, Assam, India; [email protected]
² Department of Mathematics, Swadeshi College of Commerce, Guwahati - 781007, Assam, India; [email protected]
³ Department of Computer Application (MCA), Assam Engineering College, Guwahati - 781013, Assam, India; [email protected]
*Author for correspondence
Atowar-ul Islam
Department of Computer Science and IT
Email: [email protected]

This work is licensed under a Creative Commons Attribution 4.0 International License.

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