I am working on the construction of Barnette graphs for given diameter. I would like to know the reason why many cubic 3 connected planar , (not a bipartite) are both non-Hamiltonian and Hamiltonian graphs. I found a unique property of those Hamiltonian graphs. I need the latest results related to my question.
https://www.math.ucdavis.edu/files/6313/5795/0203/DeLaTorreThesis.pdf
http://www.math.ru.nl/~bosma/Students/BarnetteFinalDocument.pdf
Actually my Aim is to hold Hamiltonian property of my graph and leaving bipartite condition. I am looking for existing (if and only if ) theorems related to my objective. Thank you for interest.
If you drop the 'bipartite' condition, then the statement indeed might not be true. Is there an example where in a non-bipartite graph, the statement fails?
Many examples we can find in Google.just type nonhamiltonian graphs in Google. There are many Hamiltonian and nonhamiltonian graphs exists without bipartite property. What is the new property of Hamiltonian cubic graphs against nonhamiltonian cubic graphs which can be verified in linear time?
I wonder then what happens to your linear-time property when the graph is bipartite too. Is it even simpler? Can it be false sometimes and help us in finding counter-examples to Barnette's conjecture? Or is it finally always true and does it finally prove the conjecture?
Either your property is not really linear in time, or it fails to decide properly whether some cubic 3 connected planar graph is hamiltonian or not, or Theorem 5.1 in the 2nd paper you attached is wrong about it being an NP-complete problem, or P = NP!
Let me explain my point through an example. we know the following theorem
Theorem: A graph is bipartite if and only if it has no odd cycle.
this results is useful to decide whether a a graph is bipartite or not
For example 1. using above theorem we can always conclude that Tree of any size is always a bipartite graph, It is always easy to check whether the graph containing an odd cycle (in linear time) like wise I am looking for a simple condition so that I can give new conjecture for 3 regular , 3 connected , planar graph to be Hamiltonian. I agree with your point on theorem 5.1. I would like to know other standard (theorems) conditions for Hamiltonian property of cubic ,3 connected, planar graph.
I have countably infinite number of Barnette graphs which are believed to be Hamiltonian and they can be classified based on ............... My current research.
If any one property of Barnatte graph is dropped it is non hamiltonion
- Badges
- Science topic
- Similar topics
- Mathematics
- Applied Mathematics