Hamiltonian decompositions of complete graphs

It is well known that K_{2n + 1} can be decomposed into n edge-disjoint Hamilton cycles. A novel method for constructing Hamiltonian decompositions of K_{2n + 1} is given and a procedure for obtaining all Hamiltonian decompositions of of K_{2n + 1} is outlined. This method is applied to find a necessary and sufficient condition for a decomposition of the edge set of K_r (r ≤ 2n) into n classes, each class consisting of disjoint paths to be extendible to a Hamiltonian decomposition of K_{2n + 1} so that each of the classes forms part of a Hamilton cycle.     

Cycle embedding in star graphs with more conditional faulty edges

The star graph is one of the most attractive interconnection networks. The cycle embedding problem is widely discussed in many networks, and edge fault tolerance is an important issue for networks since edge failures may occur when a network is put into use. In this paper, we investigate the cycle embedding problem in star graphs with conditional faulty edges. We show that there exist fault-free cycles of all even lengths from 6 to n! in any n-dimensional star graph S_n (n ? 4) with ?3n − 10 faulty edges in which each node is incident with at least two fault-free edges. Our result not only improves the previously best known result where the number of tolerable faulty edges is up to 2n − 7, but also extends the result that there exists a fault-free Hamiltonian cycle under the same condition.     

Longest cycles in r-regular r-connected graphs

Let r ≥ 3 be an integer, and ε > 0 a real number. It is shown that there is an integer N(r, ε) such that for all n ≥ N (if r is even) or for all even n ≥ N (if r is odd), there is an r-connected regular graph of valency r on exactly n vertices whose longest cycles have fewer than εn vertices. That is, the number ε > 0, no matter how small, is a “shortness coefficient” for the family of r-valent regular r-connected graphs.     

On the number of cycles possible in digraphs with large girth

We consider directed graphs which have no short cycles. In particular, if n is the number of vertices in a graph which has no cycles of length less than n ? k, for some constant k < ?n, then we show that the graph has no more than 3^k cycles. In addition, we show that for k ≤ ½n, there are graphs with exactly 3^k cycles. We thus are able to show that it is possible to bound the number of cycles possible in a graph which has no cycles of length less than f(n) by a polynomial in n if and only if f(n) ≥ n ? rlog(n) for some r.     

On the number of Hamiltonian cycles in triangulations

It is proved that if a planar triangulation different from K₃ and K₄ contains a Hamiltonian cycle, then it contains at least four of them. Together with the result of Hakimi, Schmeichel, and Thomassen [2], this yields that, for n ? 12, the minimum number of Hamiltonian cycles in a Hamiltonian planar triangulation on n vertices is four. We also show that this theorem holds for triangulations of arbitrary surfaces and for 3-connected triangulated graphs.     

The number of Hamiltonian decompositions of regular graphs

A Hamilton cycle in a graph Γ is a cycle passing through every vertex of Γ. A Hamiltonian decomposition of Γ is a partition of its edge set into disjoint Hamilton cycles. One of the oldest results in graph theory is Walecki’s theorem from the 19th century, showing that a complete graph K _n on an odd number of vertices n has a Hamiltonian decomposition. This result was recently greatly extended by Kühn and Osthus. They proved that every r-regular n-vertex graph Γ with even degree r = cn for some fixed c > 1/2 has a Hamiltonian decomposition, provided n = n(c) is sufficiently large. In this paper we address the natural question of estimating H(Γ), the number of such decompositions of Γ. Our main result is that H(Γ) = r ^(1+o(1))nr/2. In particular, the number of Hamiltonian decompositions of K _n is \({n^{\left( {1 + o\left( 1 \right)} \right){n^2}/2}}\).     

On regular graphs and Hamiltonian circuits,including answers to some questions of Joseph Zaks

A graph is called l-ply Hamiltonian if it admits l edge-disjoint Hamiltonian circuits. The following results are obtained: (1) When n ≥ 3 and 0 ≤ 2l ≤ n there exists an n-connected n-regular graph that is exactly l-ply Hamiltonian. (2) There exist 5-connected 5-regular planar graphs that are not doubly (i.e. 2-ply) Hamiltonian, one with only 132 vertices and another with only three types of face, namely 3-, 4- and 12-gons. (3) There exist 3-connected 5-regular planar graphs, one that is non-Hamiltonian and has only 76 vertices and another that has no Hamiltonian paths and has only 128 vertices. (4) There exist 5-edge-connected 5-regular planar graphs, one that is non-Hamiltonian and has only 176 vertices and another that has no Hamiltonian paths and has only 512 vertices. Result (1) was known in the special cases $\text{l = [}\text{n}\text{2}\text{]}$ (an old result) and l = 0 (due to G. H. J. Meredith, 1973). The special case l = 1 provides a negative answer to question 4 in a recent paper by Joseph Zaks and implies Corollary 1 to Zaks' Theorem 1. Results (2) and (3) involve graphs with considerably fewer vertices (and, in one case, fewer types of face) than Zaks' corresponding graphs and provide partial answers to his questions 1 and 3. Result (4) involves graphs that satisfy a stronger condition than those of Zaks but still have fewer vertices.     

How to avoid using the Regularity Lemma: Pósa’s conjecture revisited

In this paper we investigate how the use of the Regularity Lemma and the Blow-up Lemma can be avoided in certain extremal problems of dense graphs. We present the ideas for the following well-known Pósa conjecture on the square of a Hamiltonian cycle. In 1962 Pósa conjectured that any graph G of order n and minimum degree at least contains the square of a Hamiltonian cycle. In an earlier paper we proved this conjecture with the use of the Regularity Lemma-Blow-up Lemma method for n≥n₀ where n₀ is very large. Here we present another proof (and a general method) that avoids the use of the Regularity Lemma and thus the resulting n₀ is much smaller.     

Vertex-magic labelings of regular graphs II

Previously the first author has shown how to construct vertex-magic total labelings (VMTLs) for large families of regular graphs. The construction proceeds by successively adding arbitrary 2-factors to a regular graph of order n which possesses a strong VMTL, to produce a regular graph of the same order but larger size. In this paper, we exploit this construction method. We are able to show that for any r≥4, every r-regular graph of odd order n≤17 has a strong VMTL. We show how to produce strong labelings for some families of 2-regular graphs since these are used as the starting points of our construction. While even-order regular graphs are much harder to deal with, we introduce ‘mirror’ labelings which provide a suitable starting point from which the construction can proceed. We are able to show that several large classes of r-regular graphs of even order (including some Hamiltonian graphs) have VMTLs.     

Some families of integral graphs

A graph is called integral if all its eigenvalues (of the adjacency matrix) are integers. In this paper, the graphs K_1,r•K_n, r∗K_n, K_1,r•K_m,n, r∗K_m,n and the tree K_1,s•T(q,r,m,t) are defined. We determine the characteristic polynomials of these graphs and also obtain sufficient and necessary conditions for these graphs to be integral. Some sufficient conditions are found by using the number theory and computer search. All these classes are infinite. Some new results which treat interrelations between integral trees of various diameters are also found. The discovery of these integral graphs is a new contribution to the search of such graphs.     

An Ore-type condition for arbitrarily vertex decomposable graphs

Let G be a graph of order n and r, 1≤r≤n, a fixed integer. G is said to be r-vertex decomposable if for each sequence (n₁,…,n_r) of positive integers such that n₁+?+n_r=n there exists a partition (V₁,…,V_r) of the vertex set of G such that for each i∈{1,…,r}, V_i induces a connected subgraph of G on n_i vertices. G is called arbitrarily vertex decomposable if it is r-vertex decomposable for each r∈{1,…,n}.In this paper we show that if G is a connected graph on n vertices with the independence number at most ⌈n/2⌉ and such that the degree sum of any pair of non-adjacent vertices is at least n−3, then G is arbitrarily vertex decomposable or isomorphic to one of two exceptional graphs. We also exhibit the integers r for which the graphs verifying the above degree-sum condition are not r-vertex decomposable.     

The Ramsey numbers r(Pm, Kn)

This note evaluates the Ramsey numbers r(P_m,K_n), and discusses developments in 0 generalized Ramsey theory for graphs.     

The new methods for constructing matching-equivalence graphs

Two graphs G and H with order n are said to be matching-equivalent if and only if the number of r-matchings (i.e., the number of ways in which r disjoint edges can be chosen) is the same for each of the graphs G and H for each r, where 0?r?n. In this paper, the new methods for constructing ‘matching-equivalent’ graphs are given, and some families of non-matching unique graphs are also obtained.     

More orthogonal double covers of complete graphs by Hamiltonian paths

An orthogonal double cover (ODC) of the complete graph K_n by a graph G is a collection G of n spanning subgraphs of K_n, all isomorphic to G, such that any two members of G share exactly one edge and every edge of K_n is contained in exactly two members of G. In the 1980s Hering posed the problem to decide the existence of an ODC for the case that G is an almost-Hamiltonian cycle, i.e. a cycle of length n-1. It is known that the existence of an ODC of K_n by a Hamiltonian path implies the existence of ODCs of K_4n and of K_16n, respectively, by almost-Hamiltonian cycles. Horton and Nonay introduced two-colorable ODCs and showed: If there are an ODC of K_n by a Hamiltonian path for some n?3 and a two-colorable ODC of K_q by a Hamiltonian path for some prime power q?5, then there is an ODC of K_qn by a Hamiltonian path. In [U. Leck, A class of 2-colorable orthogonal double covers of complete graphs by hamiltonian paths, Graphs Combin. 18 (2002) 155-167], two-colorable ODCs of K_n and K_2n, respectively, by Hamiltonian paths were constructed for all odd square numbers n?9. Here we continue this work and construct cyclic two-colorable ODCs of K_n and K_2n, respectively, by Hamiltonian paths for all n of the form n=4k²+1 or n=(k²+1)/2 for some integer k.     

Noncrossing Hamiltonian paths in geometric graphs

A geometric graph is a graph embedded in the plane in such a way that vertices correspond to points in general position and edges correspond to segments connecting the appropriate points. A noncrossing Hamiltonian path in a geometric graph is a Hamiltonian path which does not contain any intersecting pair of edges. In the paper, we study a problem asked by Micha Perles: determine the largest number h(n) such that when we remove any set of h(n) edges from any complete geometric graph on n vertices, the resulting graph still has a noncrossing Hamiltonian path. We prove that . We also establish several results related to special classes of geometric graphs. Let h₁(n) denote the largest number such that when we remove edges of an arbitrary complete subgraph of size at most h₁(n) from a complete geometric graph on n vertices the resulting graph still has a noncrossing Hamiltonian path. We prove that . Let h₂(n) denote the largest number such that when we remove an arbitrary star with at most h₂(n) edges from a complete geometric graph on n vertices the resulting graph still has a noncrossing Hamiltonian path. We show that h₂(n)=⌈n/2⌉-1. Further we prove that when we remove any matching from a complete geometric graph the resulting graph will have a noncrossing Hamiltonian path.     

The Hamiltonian property of linear functions

Consider a digraph G(n, q, r) with n nodes and n links i → qi + r, i = 0, 1,…, n − 1, where q and r are given. The topologies of many computer networks use G(n, q, r) as basic building block. A digraph is called Hamiltonian if it contains a circuit spanning all nodes. The Hamiltonian property of a network topology provides the capability of configuring the interconnection network as a linear array, which is the configuration with the broadest practical significance, of either n − 1 or n nodes in the presence of a single faulty node or link. In this paper we give necessary and sufficient conditions for G(n, q, r) to be Hamiltonian.     

Solving the path cover problem on circular-arc graphs by using an approximation algorithm

A path cover of a graph G=(V,E) is a family of vertex-disjoint paths that covers all vertices in V. Given a graph G, the path cover problem is to find a path cover of minimum cardinality. This paper presents a simple O(n)-time approximation algorithm for the path cover problem on circular-arc graphs given a set of n arcs with endpoints sorted. The cardinality of the path cover found by the approximation algorithm is at most one more than the optimal one. By using the result, we reduce the path cover problem on circular-arc graphs to the Hamiltonian cycle and Hamiltonian path problems on the same class of graphs in O(n) time. Hence the complexity of the path cover problem on circular-arc graphs is the same as those of the Hamiltonian cycle and Hamiltonian path problems on circular-arc graphs.     

The cyclic structure of random permutations

Letα _r denote the number of cycles of length r in a random permutation, taking its values with equal probability from among the set S_n of all permutations of length n. In this paper we study the limiting behavior of linear combinations of random permutationsα ₁, ...,α _r having the form $$\zeta _{n, r} = c_{r1^{a_1 } } + ... + c_{rr} a_r $$ in the case when n, r→∞. We shall show that the class of limit distributions forξ _n,r as n, r→∞ and r In r/h→0 coincides with the class of unbounded divisible distributions. For the random variables η_n, r=α ₁+2α ₂+... rα _r, equal to the number of elements in the permutation contained in cycles of length not exceeding r, we find' limit distributions of the form r In r/n→0 and r=γ ⁿ, 0<γ<1.     

A solution of Dudeney's round table problem for an even number of people

Dudeney's round table problem asks for a set of Hamiltonian cycles in the complete graph K_n with the property that every 2-path lies on exactly one of the cycles. In this paper, we construct a solution of the problem when n is any even number.     

Graphs with maximum size and lower bounded girth

For integers n≥4 and ν≥n+1, let ex(ν;{C₃,…,C_n}) denote the maximum number of edges in a graph of order ν and girth at least n+1. The {C₃,…,C_n}-free graphs with order ν and size ex(ν;{C₃,…,C_n}) are called extremal graphs and denoted by EX(ν;{C₃,…,C_n}). We prove that given an integer k≥0, for each n≥2log₂(k+2) there exist extremal graphs with ν vertices, ν+k edges and minimum degree 1 or 2. Considering this idea we construct four infinite families of extremal graphs. We also see that minimal (r;g)-cages are the exclusive elements in EX(ν₀(r,g);{C₃,…,C_g−1}).