Total views : 216
Minimum Vertex Cover of Circulant Graph having Hamiltonian Path and its Application
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.
- 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.
This work is licensed under a Creative Commons Attribution 3.0 License.