Search

A closed curve in the Freudenthal compactification | G | of an infinite locally finite graph G is called a Hamiltonian curve if it meets every vertex of G exactly once (and hence it meets every end at least once). We prove that | G | has a Hamiltonian curve if and only if every finite vertex set of G is contained in a cycle of G . We apply this to extend a number of results and conjectures on finite graphs to Hamiltonian curves in infinite locally finite graphs. For example, Barnette’s conjecture (that every finite planar cubic 3 -connected bipartite graph is Hamiltonian) is equivalent to the statement that every one-ended planar cubic 3 -connected bipartite graph has a Hamiltonian curve. It is also equivalent to the statement that every planar cubic 3 -connected bipartite graph with a nowhere-zero 3 -flow (with no restriction on the number of ends) has a Hamiltonian curve. However, there are 7 -ended planar cubic 3 -connected bipartite graphs that do not have a Hamiltonian curve. [ABSTRACT FROM AUTHOR]

Abstract: Let be an edge-colored graph. The color degree of a vertex of , is defined as the number of colors of the edges incident to . The color number of is defined as the number of colors of the edges in . A rainbow triangle is one in which every pair of edges have distinct colors. In this paper we give some sufficient conditions for the existence of rainbow triangles in edge-colored graphs in terms of color degree, color number and edge number. As a corollary, a conjecture proposed by Li and Wang [H. Li and G. Wang, Color degree and heterochromatic cycles in edge-colored graphs, European J. Combin. 33 (2012) 1958–1964] is confirmed. [Copyright &y& Elsevier]