I have 3-regular graph G and 4-regular graph H. I can always find an Hamiltonian cycle in G and H. I am looking for a help to prove G and H are Hamiltonian.
Check these papers,
1. Li, Hao. "Generalizations of Dirac’s theorem in Hamiltonian graph theory—A survey." Discrete Mathematics (2012).
2. Elmasry, Amr, Kurt Mehlhorn, and Jens M. Schmidt. "An O (n+ m) certifying triconnnectivity algorithm for Hamiltonian graphs." Algorithmica 62.3-4 (2012): 754-766.
3. Sciriha, Irene, and Domingos Moreira Cardoso. "Necessary and sufficient conditions for a hamiltonian graph." JCMCC-Journal of Combinatorial Mathematicsand Combinatorial Computing 80 (2012): 127.
4. Ainouche, Ahmed. On sufficient conditions involving distances for hamiltonian properties in graphs. No. 2013-13. CEREGMIA, Université des Antilles et de la Guyane, 2013.
I am looking for an if and only if condition for a graph to be Hamiltonian.
In general, finding an Hamilton cycle in a graph is an NP-complete problem. But in your case, it looks like you are dealing with regular graphs. Nash-Williams Theorem says that if you have a k-regular graph on 2k+1 vertices, than it is Hamiltonian. This theorem must be in this paper
Nash-Williams, C. St. J. A. Hamiltonian circuits in graphs and digraphs. 1969 The Many Facets of Graph Theory (Proc. Conf., Western Mich. Univ., Kalamazoo, Mich., 1968) pp. 237–243 Springer, Berlin
but I have 3,and 4 regular graphs with more than 2(4)+1 vertices..Do you have any other result?
it should directly follow from Dirac's Theorem: n-vertex graph in which each vertex has degree at least n/2 must have a Hamiltonian cycle. It is well-known.
Here I have just found a survey on well-known sufficient conditions:
http://www.rose-hulman.edu/mathjournal/archives/2000/vol1-n1/paper4/v1n1-4pd.PDF
Sibel , my graph has more than 18 nodes. let me find any clue from your link
No problem Simon. Actually, I have not completely understand your question. You have a 3-regular and 4-regular graphs, and you are trying to find Hamilton cycles in them? Or is there only one graph?
I have two graphs G and H . G is 3- regular graph and H is 4- regular graphs . I can always find a Hamiltonian cycle in them. I am looking for a help to prove it mathematically. looking for a sufficient condition for my graph. I tried with few sufficient conditions in Bondy and moorthy book. It does not work for my graph. thats why looking for new sufficient conditions for my graph.
- Badges
- Science topic
- Similar topics
- Mathematics
- Applied Mathematics