×

Multiple Hamilton cycles in bipartite cubic graphs: an algebraic method. (English) Zbl 1352.05103

Summary: Many important graphs are bipartite and cubic (i.e. bipartite and trivalent, or “bicubic”). We explain concisely how the Hamilton cycles of this type of graph are characterized by a single determinantal condition over \(\mathrm{GF}(2)\). Thus algebra may be used to derive results such as those of J. Bosák [in: Theory of graphs. International symposium. Théorie des graphes. Journées internationales d’étude. Rome, juillet 1966. International Computation Centre, Rome. Centre Internationale de Calcul, Rome. New York: Gordon and Breach; Paris: Dunod. 35–46 (1967; Zbl 0183.52302)], A. Kotzig [Čas. Pěstování Mat. 83, 348–354 (1958; Zbl 0084.19602)], and W. T. Tutte [J. Lond. Math. Soc. 21, 98–101 (1946; Zbl 0061.41306)] that were originally proved differently.

MSC:

05C45 Eulerian and Hamiltonian graphs
94B05 Linear codes (general theory)
14G15 Finite ground fields in algebraic geometry
51E99 Finite geometry and special incidence structures
PDFBibTeX XMLCite
Full Text: DOI

References:

[2] Ax, J., Zeroes of polynomials over finite fields, Am. J. Math., 86, 255-261 (1964) · Zbl 0121.02003
[3] Bollobas, B., Modern Graph Theory (1998), Springer · Zbl 0902.05016
[4] Bosák, J., Hamiltonian lines in cubic graphs, (Theory of Graphs, International Symposium. Theory of Graphs, International Symposium, Rome, July 1966 (1967), Gordon & Breach: Gordon & Breach New York), 35-46
[5] Holton, D. A.; Manvel, B.; McKay, B. D., Hamilton cycles in cubic 3-connected bipartite planar graphs, J. Comb. Theory, Ser. B, 38, 279-297 (1985) · Zbl 0551.05052
[6] Kotzig, A., Bemerkung zu den Faktorenzerlegungen der endlichen paaren regulären Graphen, Čas. Pěst. Math., 87, 348-354 (1958) · Zbl 0084.19602
[7] Lidl, R.; Niederreiter, H., Finite Fields, Encycl. Math. Appl., vol. 20 (1984), Cambridge Uni. Press: Cambridge Uni. Press Cambridge
[8] Tutte, W. T., On Hamilton circuits, J. Math. Soc., 21, 98-101 (1946) · Zbl 0061.41306
[9] Warning, E., Bemerkung zur vorstehenden Arbeit von Herrn Chevalley, Abh. Math. Semin. Univ. Hamb., 11, 76-83 (1936) · JFM 61.1043.02
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.