Total views : 216

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


  • Department of Computer Science and IT, Cotton College, Guwahati - 781001, Assam, India
  • Department of Mathematics, Swadeshi College of Commerce, Guwahati - 781013, Assam, India
  • 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.


Circulant Graph, Complete Graph, Deadlock, Minimum Vertex Cover, Process, Resources.

Full Text:

 |  (PDF views: 208)


  • Choudhury JK, Das A, Kalita B. Decomposition of complete graphs in to circulant graph and its application. IAEME. 2013; 4(6):25–47.
  • El-Zanati S, King K, Mudrock J. On the cyclic decomposition of circulant graphs into almost-bipartite graphs. Australian Journal of Combinatorics. 2011; 49:61–76.
  • Bermond JC, Favaron O, Maheo M. Hamiltonian decomposition of cayley graphs of degree. Journal of Combinatorial Theory, Series B. 1989; 46(2):142–53.
  • Anitha R, Lekshmi RS. N-sun decomposition of complete graphs and complete bipartite graphs. World Academy of Science, Engineering and Technology. 2007; 21(3):262–6.
  • Shyu TW. Decomposition of complete graphs into cycles and stars. Graphs and Combinatorics. 2011; 29(2):301–13.
  • Froncek D. Decomposition of complete graphs into small graphs. Opuscula Mathematica. 2010; 30(3):277–80.
  • Fu HL, Hwang FK, Jimbo M, Mutoh Y, Shiue CL. Decomposition of complete graphs into r c K ×K ’s. Journal of Statistical Planning and Inference. 2004; 119(2):225–36.
  • Gerace I, Greco F. The traveling salesman problem in symmetric circulant matrices with two stripes. Math Structures in Comp Science. 2008; 18(1):1–11.
  • Islam AU, kalita B, Dutta A. Minimum vertex cover of different regular planar graphs and its application. International Journal of Mathematical Archive. 2014; 5(10):175–84. ISSN: 2229-5046.
  • Mary AA, Amutha A. Slope number on complete graphs. Indian Journal of Science and Technology. 2016 Jun; 9(22):1–4.
  • Manesh S. K-ordered hamiltonian graphs. Indian Journal of Science and Technology. 2014 Mar; 7(3S):28–9.
  • Nadjafikhah M, Kabi-Nejad P. Conservation laws and hamiltonian symmetries of whitham-broer-kaup equations. Indian Journal of Science and Technology. 2015 Jan; 8(2):178–84.


  • There are currently no refbacks.

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.