Paper title: Beyond Grinberg Equation in cubic planar graphs
DOI: https://doi.org/10.4316/JACSM.201901003
Published in: Issue 1, (Vol. 13) / 2019Download
Publishing date: 2019-04-16
Pages: 19-24
Author(s): ONETE Cristian E., ONETE Maria-Cristina C.
Abstract. In this paper, Grinberg equation related to the Hamiltonicity of cubic planar graphs is revisited using the cycle base description of the graph and the related Laplacian. The advantages and the limitations of a pure Algebraic approach to Hamiltonicity are shown. Examples, showing the limitations are presented, too. Further possible approaches are suggested. Some unexpected results are shown, too
Keywords: Planar Graphs, Hamiltonicity, Cycles Base, Grinberg Equation, Laplacian, Hamiltonian Cycle
References:1. A. Bondy, U.S.R. Murty, "Graph Theory", Springer Graduate Texts in Mathematics, 2008.
2. MacLane, S.," A combinatorial condition for planar graphs", Fundamenta Mathematicae 28, pp. 22–32, 1937.
3. G. Kirchhoff, cber die Au&sung der Gleichungen, auf welche man bei der Untersuchung der linearen Verteilung galvanischer Strijme gefuhrt wird, Ann. Phys. Chem. 72:497-508 (1847).
4. N. Balabanian and T.A. Bickart, "Electrical Network Theory", John Wiley and Sons, Inc., Ch. 3.6, 1969.
5. Grinberg, È. Ja. (1968), "Plane homogeneous graphs of degree three without Hamiltonian circuits", Latvian Math. Yearbook 4 (in Russian), Riga: Izdat. "Zinatne", pp. 51–58, MR 0238732. English translation by Dainis Zeps, arXiv:0908.2563.
6. C.E.Onete and M.C.C.Onete:" Building Hamiltonian Networks Using The Cycles Laplacian Of The Underlying Graph", ISCAS 2015, 2015 IEEE International Symposium on, pp.145-148, 24-27 May, 2015, doi: 10.1109/ISCAS.2015.716859.
7. Onete, C.E.; Onete, M.C.C., "Finding ground traces using the Laplacian of the meshes of the associated graph," in SOC Conference (SOCC), 2013 IEEE 26th International , pp.336-341, 4-6 Sept. 2013, doi: 0.1109/SOCC.2013.6749712.
8. Andrews, George E.," Number Theory", Dover Publications, Inc. New York, 1994.
9. Gunnar Brinkmann, Jan Goedgebeur, Brendan D. McKay," Generation of Cubic graphs", Discrete Mathematics and Theoretical Computer Science, DMTCS vol. 13:2, pp.69–80, 2011
10. Faulkner, G.B., Younger, D.H.,"Non-Hamiltonian Planar Maps", Discrete Mathematics 7, North-Holland Publishing Company, 1974, pp.67-74.
11. Gross, J.L., Yellen, J.,"Graph Theory and its Applications", Chapman & Hall/CRC, second edition, 2006.
12. Schwerdtfeger, P., Wirz, L.N., Avery, J., WIREs Comput Mol Sci 2015, 5:96–145. doi: 10.1002/wcms.1207.
Back to the journal content
Creative Commons License
This article is licensed under a
Creative Commons Attribution-ShareAlike 4.0 International License.
Home | Editorial Board | Author info | Archive | Contact
Copyright JACSM 2007-2019