Cycles and paths in edge‐colored graphs with given degrees

Sufficient degree conditions for the existence of properly edge‐colored cycles and paths in edge‐colored graphs, multigraphs and random graphs are investigated. In particular, we prove that an edge‐colored multigraph of order n on at least three colors and with minimum colored degree greater than or equal to ?(n+1)/2? has properly edge‐colored cycles of all possible lengths, including hamiltonian cycles. Longest properly edge‐colored paths and hamiltonian paths between given vertices are considered as well. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 63–86, 2010     

Highly-connected planar cubic graphs with few or many Hamilton cycles

In this paper we consider the number of Hamilton cycles in planar cubic graphs of high cyclic edge-connectivity, answering two questions raised by Chia and Thomassen (2012) about extremal graphs in these families. In particular, we find families of cyclically 5-edge-connected planar cubic graphs with more Hamilton cycles than the generalized Petersen graphs $P(2n,2)$. The graphs themselves are fullerene graphs that correspond to certain carbon molecules known as nanotubes—more precisely, the family consists of the zigzag nanotubes of (fixed) width 5and increasing length. In order to count the Hamilton cycles in the nanotubes, we develop methods inspired by the transfer matrices of statistical physics. We outline how these methods can be adapted to count the Hamilton cycles in nanotubes of greater (but still fixed) width, with the caveat that the resulting expressions involve matrix powers. We also consider cyclically 4-edge-connected planar cubic graphs with few Hamilton cycles, and exhibit an infinite family of such graphs each with exactly 4 Hamilton cycles. Finally we consider the “other extreme” for these two classes of graphs, thus investigating cyclically 4-edge-connected planar cubic graphs with many Hamilton cycles and the cyclically 5-edge-connected planar cubic graphs with few Hamilton cycles. In each of these cases, we present partial results, examples and conjectures regarding the graphs with few or many Hamilton cycles.     

Nested cycles in large triangulations and crossing-critical graphs

We show that every sufficiently large plane triangulation has a large collection of nested cycles that either are pairwise disjoint, or pairwise intersect in exactly one vertex, or pairwise intersect in exactly two vertices. We apply this result to show that for each fixed positive integer k, there are only finitely many k-crossing-critical simple graphs of average degree at least six. Combined with the recent constructions of crossing-critical graphs given by Bokal, this settles the question of for which numbers q>0 there is an infinite family of k-crossing-critical simple graphs of average degree q.     

Minimum-weight cycle covers and their approximability

A cycle cover of a graph is a set of cycles such that every vertex is part of exactly one cycle. An L-cycle cover is a cycle cover in which the length of every cycle is in the set L⊆N.We investigate how well L-cycle covers of minimum weight can be approximated. For undirected graphs, we devise non-constructive polynomial-time approximation algorithms that achieve constant approximation ratios for all sets L. On the other hand, we prove that the problem cannot be approximated with a factor of 2−ε for certain sets L.For directed graphs, we devise non-constructive polynomial-time approximation algorithms that achieve approximation ratios of O(n), where n is the number of vertices. This is asymptotically optimal: We show that the problem cannot be approximated with a factor of o(n) for certain sets L.To contrast the results for cycle covers of minimum weight, we show that the problem of computing L-cycle covers of maximum weight can, at least in principle, be approximated arbitrarily well.     

Periodic paths on nonautonomous graphs

We define nonautonomous graphs as a class of dynamic graphs in discrete time whose time-dependence consists in connecting or disconnecting edges. We study periodic paths in these graphs, and the associated zeta functions. Based on the analytic properties of these zeta functions we obtain explicit formulae for the number of n-periodic paths, as the sum of the nth powers of some specific algebraic numbers.     

Twofold 2-perfect bowtie systems with an extra property

A bowtie is a closed trail whose graph consists of two 3-cycles with exactly one vertex in common. A 2-fold bowtie system of order n is an edge-disjoint decomposition of 2K _n into bowties. A 2-fold bowtie system is said to be 2-perfect provided that every pair of distinct vertices is joined by two paths of length 2. It is said to be extra provided these two paths always have distinct midpoints. The extra property guarantees that the two paths x, a, y and x, b, y between every pair of vertices form a 4-cycle (x, a, y, b), and that the collection of all such 4-cycles is a four-fold 4-cycle system. We show that the spectrum for extra 2-perfect 2-fold bowtie systems is precisely the set of all n ?? 0 or 1 (mod 3), ${n\,\geqslant\,6}$ . Additionally, with an obvious definition, we show that the spectrum for extra 2-perfect 2-fold maximum packings of 2K _n with bowties is precisely the set of all n ?? 2 (mod 3), ${n\,\geqslant\,8}$ .     

Optimal covers with Hamilton cycles in random graphs

A packing of a graph G with Hamilton cycles is a set of edge-disjoint Hamilton cycles in G. Such packings have been studied intensively and recent results imply that a largest packing of Hamilton cycles in G _n,p a.a.s. has size ?δ(G _n,p )/2?. Glebov, Krivelevich and Szabó recently initiated research on the ‘dual’ problem, where one asks for a set of Hamilton cycles covering all edges of G. Our main result states that for \(\tfrac{{log^{117} n}} {n} \leqslant p \leqslant 1 - n^{ - 1/8}\) , a.a.s. the edges of G _n,p can be covered by ?Δ (G _n,p )/2? Hamilton cycles. This is clearly optimal and improves an approximate result of Glebov, Krivelevich and Szabó, which holds for p ≥ n ^?1+?. Our proof is based on a result of Knox, Kühn and Osthus on packing Hamilton cycles in pseudorandom graphs.     

Multigraphs with quasiweak odd cycles

In this paper we define a class of multigraphs with chromatic index equal to the maximum degree d. They are characterized by a property of their elementary odd cycles. It is shown that these graphs are panchromatic (i.e., they have a good k-coloring for any k). In the partially ordered set of color-feasible sequences of these graphs, all maximal sequences have at most d + 1 terms.     

Minimum genus embeddings of the complete graph

In this paper,the problem of construction of exponentially many minimum genus embeddings of complete graphs in surfaces are studied.There are three approaches to solve this problem.The first approach is to construct exponentially many graphs by the theory of graceful labeling of paths;the second approach is to find a current assignment of the current graph by the theory of current graph;the third approach is to find exponentially many embedding(or rotation) schemes of complete graph by finding exponentially many distinct maximum genus embeddings of the current graph.According to this three approaches,we can construct exponentially many minimum genus embeddings of complete graph K_(12s+8) in orientable surfaces,which show that there are at least 10/3×(200/9)~s distinct minimum genus embeddings for K_(12s+8) in orientable surfaces.We have also proved that K_(12s+8) has at least 10/3×(200/9)~s distinct minimum genus embeddings in non-orientable surfaces.     

Planar Ramsey numbers for cycles

For two given graphs G and H the planar Ramsey number PR(G,H) is the smallest integer n such that every planar graph F on n vertices either contains a copy of G or its complement contains a copy H. By studying the existence of subhamiltonian cycles in complements of sparse graphs, we determine all planar Ramsey numbers for pairs of cycles.     

Identities for non-crossing graphs and multigraphs

We refine an identity between the numbers of certain non-crossing graphs and multigraphs, by modifying a bijection found by P. Podbrdský [A bijective proof of an identity for noncrossing graphs, Discrete Math. 260 (2003) 249-253]. We also prove a new identity between the number of acyclic non-crossing graphs with n vertices and k edges (isolated vertices allowed and no multiple edges allowed), and the number of non-crossing connected graphs with n edges and k vertices (multiple edges allowed and no isolated vertices allowed).     

Long cycles in graphs without hamiltonian paths

For a graph G, p(G) and c(G) denote the order of a longest path and a longest cycle of G, respectively. Bondy and Locke [J.A. Bondy, S.C. Locke, Relative length of paths and cycles in 3-connected graphs, Discrete Math. 33 (1981) 111-122] consider the gap between p(G) and c(G) in 3-connected graphs G. Starting with this result, there are many results appeared in this context, see [H. Enomoto, J. van den Heuvel, A. Kaneko, A. Saito, Relative length of long paths and cycles in graphs with large degree sums, J. Graph Theory 20 (1995) 213-225; M. Lu, H. Liu, F. Tian, Relative length of longest paths and cycles in graphs, Graphs Combin. 23 (2007) 433-443; K. Ozeki, M. Tsugaki, T. Yamashita, On relative length of longest paths and cycles, preprint; I. Schiermeyer, M. Tewes, Longest paths and longest cycles in graphs with large degree sums, Graphs Combin. 18 (2002) 633-643]. In this paper, we investigate graphs G with p(G)−c(G) at most 1 or at most 2, but with no hamiltonian paths. Let G be a 2-connected graph of order n, which has no hamiltonian paths. We show two results as follows: (i) if , then p(G)−c(G)≤1, and (ii) if σ₄(G)≥n+3, then p(G)−c(G)≤2.     

Some small ramsey numbers

In previous work, the Ramsey numbers have been evaluated for all pairs of graphs with at most four points. In the present note, Ramsey numbers are tabulated for pairs F₁, F₂ of graphs where F₁ has at most four points and F₂ has exactly five points. Exact results are listed for almost all of these pairs.     

Steiner Triple Systems,Pinched Surfaces,and Complete Multigraphs

We consider complete multigraphs \({K_n^m}\) on n vertices with every pair joined by m edges. We embed these graphs to triangulate \({S_n^k}\) , a pinched surface with n pinch points each having k sheets. These embeddings have a vertex at each pinch point and any two sheets at a pinch point have the same number of edges. Moreover, we want to 2m-color the faces such that each color class is a Steiner triple system. These embeddings generalize in two ways biembeddings of Steiner triple systems, the case m =  1, k =  1 of simple graphs in surfaces without pinch points.     

The spectral radius of graphs without paths and cycles of specified length

Let G be a graph with n vertices and μ(G) be the largest eigenvalue of the adjacency matrix of G. We study how large μ(G) can be when G does not contain cycles and paths of specified order. In particular, we determine the maximum spectral radius of graphs without paths of given length, and give tight bounds on the spectral radius of graphs without given even cycles. We also raise a number of open problems.     

On n-partite Tournaments with Unique n-cycle

An n-partite tournament is an orientation of a complete n-partite graph. An n-partite tournament is a tournament, if it contains exactly one vertex in each partite set. Douglas, Proc. London Math. Soc. 21 (1970) 716–730, obtained a characterization of strongly connected tournaments with exactly one Hamilton cycle (i.e., n-cycle). For n≥3, we characterize strongly connected n-partite tournaments that are not tournaments with exactly one n-cycle. For n≥5, we enumerate such non-isomorphic n-partite tournaments.     

On infinite graphs with a specified number of colorings

In this paper we construct a planar graph of degree four which admits exactly N_u 3-colorings, we prove that such a graph must have degree at least four, and we consider various generalizations. We first allow our graph to have either one or two vertices of infinite degree and/or to admit only finitely many colorings and we note how this effects the degrees of the remaining vertices. We next consider n-colorings for n>3, and we construct graphs which we conjecture (but cannot prove) are of minimal degree. Finally, we consider nondenumerable graphs, and for every 3 <n<ω and every infinite cardinal k we construct a graph of cardinality k which admits exactly kn-colorings. We also show that the number of n-colorings of a denumerable graph can never be strictly between N_u and 2^N_u and that an appropriate generalization holds for at least certain nondenumerable graphs.     

Hamilton cycles in claw-heavy graphs

A graph G on n≥3 vertices is called claw-heavy if every induced claw (K_1,3) of G has a pair of nonadjacent vertices such that their degree sum is at least n. In this paper we show that a claw-heavy graph G has a Hamilton cycle if we impose certain additional conditions on G involving numbers of common neighbors of some specific pair of nonadjacent vertices, or forbidden induced subgraphs. Our results extend two previous theorems of Broersma, Ryjá?ek and Schiermeyer [H.J. Broersma, Z. Ryjá?ek, I. Schiermeyer, Dirac’s minimum degree condition restricted to claws, Discrete Math. 167-168 (1997) 155-166], on the existence of Hamilton cycles in 2-heavy graphs.     

On Hamilton decompositions of infinite circulant graphs

The natural infinite analog of a (finite) Hamilton cycle is a two‐way‐infinite Hamilton path (connected spanning 2‐valent subgraph). Although it is known that every connected 2k‐valent infinite circulant graph has a two‐way‐infinite Hamilton path, there exist many such graphs that do not have a decomposition into k edge‐disjoint two‐way‐infinite Hamilton paths. This contrasts with the finite case where it is conjectured that every 2k‐valent connected circulant graph has a decomposition into k edge‐disjoint Hamilton cycles. We settle the problem of decomposing 2k‐valent infinite circulant graphs into k edge‐disjoint two‐way‐infinite Hamilton paths for , in many cases when , and in many other cases including where the connection set is or .