Powers of cycles, powers of paths, and distance graphs

In 1988, Golumbic and Hammer characterized the powers of cycles, relating them to circular arc graphs. We extend their results and propose several further structural characterizations for both powers of cycles and powers of paths. The characterizations lead to linear-time recognition algorithms of these classes of graphs. Furthermore, as a generalization of powers of cycles, powers of paths, and even of the well-known circulant graphs, we consider distance graphs. While the colorings of these graphs have been intensively studied, the recognition problem has been so far neglected. We propose polynomial-time recognition algorithms for these graphs under additional restrictions.     

双圈覆盖问题

Seyntour[1]与Szekeres[5]猜想，每一个无割边的图G具有一个圈集合 使G中的每个边存在于 的两个圈中。本证明此猜想成立当且仅当它对没有非平凡的三个边割的图成立。     

Two Hamiltonian cycles

If the line graph of a graph G decomposes into Hamiltonian cycles, what is G? We answer this question for decomposition into two cycles.     

双圈图的色多项式的计算

通过对双圈图两种不同情形的讨论，解决了双圈图的色多项式的计算问题。     

Hypohamiltonian Planar Cubic Graphs with Girth 5

A graph is called hypohamiltonian if it is not hamiltonian but becomes hamiltonian if any vertex is removed. Many hypohamiltonian planar cubic graphs have been found, starting with constructions of Thomassen in 1981. However, all the examples found until now had 4‐cycles. In this note we present the first examples of hypohamiltonian planar cubic graphs with cyclic connectivity 5, and thus girth 5. We show by computer search that the smallest members of this class are three graphs with 76 vertices.     

Ring graphs and complete intersection toric ideals

We study the family of graphs whose number of primitive cycles equals its cycle rank. It is shown that this family is precisely the family of ring graphs. Then we study the complete intersection property of toric ideals of bipartite graphs and oriented graphs. An interesting application is that complete intersection toric ideals of bipartite graphs correspond to ring graphs and that these ideals are minimally generated by Gröbner bases. We prove that any graph can be oriented such that its toric ideal is a complete intersection with a universal Gröbner basis determined by the cycles. It turns out that bipartite ring graphs are exactly the bipartite graphs that have complete intersection toric ideals for any orientation.     

Light graphs in families of polyhedral graphs with prescribed minimum degree, face size, edge and dual edge weight

A graph H is defined to be light in a family H of graphs if there exists a finite number φ(H,H) such that each G∈H which contains H as a subgraph, contains also a subgraph K≅H such that the Δ_G(K)≤φ(H,H). We study light graphs in families of polyhedral graphs with prescribed minimum vertex degree δ, minimum face degree ρ, minimum edge weight w and dual edge weight w^∗. For those families, we show that there exists a variety of small light cycles; on the other hand, we also present particular constructions showing that, for certain families, the spectrum of short cycles contains irregularly scattered cycles that are not light.     

Cycle decompositions III: Complete graphs and fixed length cycles

We show that the necessary conditions for the decomposition of the complete graph of odd order into cycles of a fixed even length and for the decomposition of the complete graph of even order minus a 1‐factor into cycles of a fixed odd length are also sufficient. © 2002 John Wiley & Sons, Inc. J Combin Designs 10: 27–78, 2002     

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.     

Short cycle structures for graphs on surfaces and an open problem of Mohar and Thomassen

In this paper we investigate cycle base structures of a (weighted) graph and show that much information of short cycles is contained in an MCB (i.e., minimum cycle base). After setting up a Hall type theorem for base-transformation, we give a sufficient and necessary condition for a cycle base to be an MCB. Furthermore, we show that the structure of MCB in a (weighted) graph is unique. The property is also true for those having a longest length (although much work has been down in evaluating MCB, little is known for those having a longest length). We use those methods to find out some unknown properties for short cycles sharing particular properties in (unweighted) graphs. As applications, we determine the structures of short cycles in an embedded graph and show that there exist polynomially bounded algorithms in finding a shortest contractible cycle and a shortest two-sided cycle provided such cycles exist. Those answer an open problem of B. Mohar and C. Thomassen.     

On the number of hamiltonian cycles in triangulations with few separating triangles

In this article, we investigate the number of hamiltonian cycles in triangulations. We improve a lower bound of for the number of hamiltonian cycles in triangulations without separating triangles (4‐connected triangulations) by Hakimi, Schmeichel, and Thomassen to a linear lower bound and show that a linear lower bound even holds in the case of triangulations with one separating triangle. We confirm their conjecture about the number of hamiltonian cycles in triangulations without separating triangles for up to 25 vertices and give computational results and constructions for triangulations with a small number of hamiltonian cycles and 1–5 separating triangles.     

K3-free图的线图的哈密顿性

设G是一个简单图，Gi G，G1在G中的度定义为d（Gt）=∑v∈v（c）d（v），其中d（v）为v在G中的度数。本文的主要结果是：设G是n≥2阶几乎无桥的简单连通K3-free图，且G≌k1,n-1、Q1和Q2，若对G中任何同构于四个顶点路的导出子图I有d（I）≥n＋2，则G有一个D-闭迹，从而G的线图L（G）是哈密顿图。     

The arithmetical rank of the edge ideals of cactus graphs

We prove that, for the edge ideal of a cactus graph, the arithmetical rank is bounded above by the sum of the number of cycles and the maximum height of its associated primes. The bound is sharp, but in many cases, it can be improved. Moreover, we show that the edge ideal of a Cohen–Macaulay graph that contains exactly one cycle or is chordal or has no cycles of length 4 and 5 is a set-theoretic complete intersection.     

Decomposing complete equipartite graphs into short even cycles

In this article we find necessary and sufficient conditions to decompose a complete equipartite graph into cycles of uniform length, in the case that the length is both even and short relative to the number of parts. © 2010 Wiley Periodicals, Inc. J Combin Designs 19:131‐143, 2011     

On even cycle decompositions of line graphs of cubic graphs

An even cycle decomposition of a graph is a partition of its edges into cycles of even length. In 2012, Markström conjectured that the line graph of every 2-connected cubic graph has an even cycle decomposition and proved this conjecture for cubic graphs with oddness at most 2. However, for 2-connected cubic graphs with oddness 2, Markström only considered these graphs with a chordless 2-factor. (A chordless 2-factor of a graph is a 2-factor consisting of only induced cycles.) In this paper, we first construct an infinite family of 2-connected cubic graphs with oddness 2 and without chordless 2-factors. We then give a complete proof of Markström’s result and further prove this conjecture for cubic graphs with oddness 4.     

Distance unimodular equivalence of graphs

Let G be a connected graph and D(G) be its distance matrix. In this article, the Smith normal forms of the integer matrices D(G) are determined for trees, wheels, cycles, complements of cycles and are reduced for complete multipartite graphs.     

The Hamilton–Waterloo problem for cycle sizes 3 and 4

The Hamilton–Waterloo problem seeks a resolvable decomposition of the complete graph K_n, or the complete graph minus a 1‐factor as appropriate, into cycles such that each resolution class contains only cycles of specified sizes. We completely solve the case in which the resolution classes are either all 3‐cycles or 4‐cycles, with a few possible exceptions when n=24 and 48. © 2009 Wiley Periodicals, Inc. J Combin Designs 17: 342–352, 2009     

Graph homomorphisms through random walks

In this paper we introduce some general necessary conditions for the existence of graph homomorphisms, which hold in both directed and undirected cases. Our method is a combination of Diaconis and Saloff–Coste comparison technique for Markov chains and a generalization of Haemers interlacing theorem. As some applications, we obtain a necessary condition for the spanning subgraph problem, which also provides a generalization of a theorem of Mohar (1992) as a necessary condition for Hamiltonicity. In particular, in the case that the range is a Cayley graph or an edge‐transitive graph, we obtain theorems with a corollary about the existence of homomorphisms to cycles. This, specially, provides a proof of the fact that the Coxeter graph is a core. Also, we obtain some information about the cores of vertex‐transitive graphs. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 15–38, 2003     

Cycle decompositions of complete multigraphs

It is shown that the obvious necessary conditions for the existence of a decomposition of the complete multigraph with n vertices and with λ edges joining each pair of distinct vertices into m‐cycles, or into m‐cycles and a perfect matching, are also sufficient. This result follows as an easy consequence of more general results which are obtained on decompositions of complete multigraphs into cycles of varying lengths. © 2010 Wiley Periodicals, Inc. J Combin Designs 19:42‐69, 2010     

Infinite paths in planar graphs IV,dividing cycles

Nash‐Williams conjectured that a 4‐connected infinite planar graph contains a spanning 2‐way infinite path if, and only if, the deletion of any finite set of vertices results in at most two infinite components. In this article, we prove this conjecture for graphs with no dividing cycles and for graphs with infinitely many vertex disjoint dividing cycles. A cycle in an infinite plane graph is called dividing if both regions of the plane bounded by this cycle contain infinitely many vertices of the graph. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 173–195, 2006