In 1969 , David Barnette conjectured that 3 regular , 3-connected , bipartite , planar graph is Hamiltonian. . I am interested to generate Barnette graph for given even number of vertices. There are countably finite number of Barnette graphs available in the literature.
Consider a grid graph with 4 vertices (cycle C 4) which is Hamiltonian. Increasing dimension in one direction , we see that the resulting graph is always Hamiltonian but not Barnette. Can one generate countably infinite number of Barnette graphs from one small Barnette graph?
Dear Dr. Simon Raj
Please find the following attachments on Barnette Conjecture and Barnette Graphs. Hope that these articles will help you find a solution to your problem.
https://www.math.ucdavis.edu/files/6313/5795/0203/DeLaTorreThesis.pdf
http://www.math.ru.nl/~bosma/Students/BarnetteFinalDocument.pdf
http://theory.stanford.edu/~tomas/barnew.pdf
http://ajc.maths.uq.edu.au/pdf/20/ocr-ajc-v20-p111.pdf
This is a good question.
A study of Barnette's 3-connected cubic planar graphs is given in
J. Goedgebeur, Generation algorithms for mathematical and chemical problems, Ph.D. thesis, Ghent University, 2013:
http://caagt.ugent.be/jgoedgeb/Thesis_Jan_Goedgebeur.pdf
See Section 4.4.2, page 122, on Barnette's 1969 conjecture: Every 3-connected cubic planar graph with face size 6 is Hamiltonian. Barnette's conjecture was checked for 3-connected planar graphs with up to 316 vertices.
Thank you Dr. Sudave and Dr.James. The thesis attached by Dr.James and last paper by Dr.Sudev are useful and new research articles for me. Thank you. but I am looking for countably infinite Barnette graphs from one family of graphs. There are countably finite graphs but they are neither derived from one single graph nor from one family of graphs. I am also interested to know the usefulness
( applications) of Barnette graphs in different field of engineering and sciences. Now i modify my question.
1.For a given even number 2k greater than 336 , can one generate a Barnette graph of size 2k?
and
2.Can one find a one to one correspondence between set of Barnette graphs and the set of even numbers ?
It has been shown that fullerenes are hamiltonian [1] and they form an infinite family of cubic, 3-connected, planar graphs with faces of size at most 6. There is at least one fullerene on 2k vertices for each k greater than 11. Of course these are not bipartite since they contain pentagons, so I guess you are mainly interested in the other Barnette's conjecture. But, the thesis by Jan Goedgebeur also talks about this second conjecture and not the one about bipartite graphs.
[1] http://arxiv.org/abs/1409.2440
Thank you Nicolas. i am looking for Barnette graphs of size 2k for given even number 2k greater than 336. And how do you count fullerene garphs?. Can one give applications of those networks?
Fullerenes are actually a class of carbon molecules which have received much attention from chemists in the last twenty to thirty years. As graphs they correspond to cubic planar graphs with all faces hexagons or pentagons. For the generation I would refer to the thesis of Jan Goedgebeur which is linked above. Chapter for is about the generation of fullerenes. The references given in there should also be useful.
Than you, Nicolas . can you add chemistry research paper about carbon molecules mentioning graph theory concepts ( fullerene) ?
Just a small selection:
H.W. Kroto, J.R. Heath, S.C. O'Brien, R.F. Curl, and R.E. Smalley. C60: Buckminsterfullerene. Nature, 318(6042):162-163, 1985.
X. Liu, D.J. Klein, T.G. Schmalz, and W.A. Seitz. Generation of carbon cage polyhedra.
Journal of Computational Chemistry, 12(10):1252-1259,1991.
D.E. Manolopoulos and J.C. May. Theoretical studies of the fullerenes: C34 to C70. Chemical Physics Letters, 181:105-111, 1991.
D.E. Manolopoulos and P.W. Fowler. A fullerene without a spiral. Chemical Physics Letters, 204(1-2):1-7, 1993.
P.W. Fowler and D.E. Manolopoulos. An atlas of fullerenes. International series of monographs on chemistry. Clarendon Press, 1995.
And maybe more an answer to your original question: all prisms with an even base are hamiltonian, cubic, 3-connected, bipartite, planar graphs with 4k vertices and they exist for each k>=2.
does it contain less diameter(communication delay) ? Can you attach a graph?
The diameter increases as the size of the base increases. For examples you can have a look at the wikipedia page: https://en.wikipedia.org/wiki/Prism_graph
Thank you Nicolas. Extending the graph by Increase vertices is not possible for the graphs you have sent. And the diameter is not minimum with respect to the number of vertices.
The diameter is certainly not minimal. I don't know if you will easily find a family of graphs that is easily described, satisfy the conditions of the conjecture and has a minimal diameter for its number of vertices.
What do you mean by the graph cannot be extended by increasing the vertices? Prisms exist for any even number of vertices, and the ones where the order is divisible by four satisfy the conditions of the conjecture. Do you have a specific extension in mind?
- Badges
- Science topic
- Similar topics
- Mathematics
- Applied Mathematics