An algorithm for finding hamilton cycles in random directed graphs

We describe a polynomial (O(n^1.5)) time algorithm DHAM for finding hamilton cycles in digraphs. For digraphs chosen uniformly at random from the set of digraphs with vertex set {1, 2, …, n} and m = m(n) edges the limiting probability (as n → ∞) that DHAM finds a hamilton cycle equals the limiting probability that the digraph is hamiltonian. Some applications to random “travelling salesman problems” are discussed.     

Maximal sets of hamilton cycles in complete multipartite graphs

A set S of edge‐disjoint hamilton cycles in a graph G is said to be maximal if the edges in the hamilton cycles in S induce a subgraph H of G such that G ? E(H) contains no hamilton cycles. In this context, the spectrum S(G) of a graph G is the set of integers m such that G contains a maximal set of m edge‐disjoint hamilton cycles. This spectrum has previously been determined for all complete graphs and for all complete bipartite graphs. In this paper, we extend these results to the complete multipartite graphs. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 49–66, 2003     

Factorizations of product graphs into cycles of uniform length

The following question is raised by Alspach, Bermond and Sotteau: IfG ₁ has a decomposition into hamilton cycles and a 1-factor, andG ₂ has a hamilton cycle decmposition (HCD), does their wreath productG ₁ *G ₂ admit a hamilton cycle decomposition? In this paper the above question is answered with an additional condition onG ₁. Further it is shown that some product graphs can be decomposed into cycles of uniform length, that is, the edge sets of the graphs can be partitioned into cycles of lengthk, for some suitablek.     

An algorithm for finding hamilton paths and cycles in random graphs

This paper describes a polynomial time algorithm HAM that searches for Hamilton cycles in undirected graphs. On a random graph its asymptotic probability of success is that of the existence of such a cycle. If all graphs withn vertices are considered equally likely, then using dynamic programming on failure leads to an algorithm with polynomial expected time. The algorithm HAM is also used to solve the symmetric bottleneck travelling salesman problem with probability tending to 1, asn tends to ∞. Various modifications of HAM are shown to solve several Hamilton path problems. Supported by NSF Grant MCS 810 4854.     

Super-connected edge transitive graphs

A graph G is said to be super-connected if any minimum cut of G isolates a vertex. In a previous work due to the second author of this note, super-connected graphs which are both vertex transitive and edge transitive are characterized. In this note, we generalize the characterization to edge transitive graphs which are not necessarily vertex transitive, showing that the only irreducible edge transitive graphs which are not super-connected are the cycles C_n(n?6) and the line graph of the 3-cube, where irreducible means the graph has no vertices with the same neighbor set. Furthermore, we give some sufficient conditions for reducible edge transitive graphs to be super-connected.     

Expected numbers at hitting times

We determine exactly the expected number of hamilton cycles in the random graph obtained by starting with n isolated vertices and adding edges at random until each vertex degree is at least two. This complements recent work of Cooper and Frieze. There are similar results concerning expected numbers, for example, of perfect matchings, spanning trees, hamilton paths, and directed hamilton cycles.     

Heuristics for unequal weight delivery problems with a fixed error guarantee

This paper presents heuristics that are based on optimal partitioning of a travelling salesman tour, for solving the unequal weight delivery problem. The worst case error performance is given as a bound on the worst case ratio of the cost of the heuristic solution to the cost of the optimal solution. A fully polynomial procedure which consists of applying the optimal partitioning to a travelling salesman tour generated by Christofides' heuristic has a worst case error bound of 3.5−3/Q where Q is the capacity limit of the vehicles. When optimal partitioning is applied to an optimal travelling salesman tour, the worst case error bound becomes 3−2/Q.     

On shortest cocycle covers of graphs

A cocycle (resp. cycle) cover of a graph G is a family C of cocycles (resp. cycles) of G such that each edge of G belongs to at least one member of C. The length of C is the sum of the cardinalities of its members. While it is known (see [5, 6]) that every bridgeless graph G = (V, E) has a cycle cover of length not greater than $\text{5}\text{3}\text{|E|}$, it is shown that there exists no α < 2 such that every loopless graph G = (V, E) has a cocycle cover with length not greater than α |E|. To do this, cocycle covers of minimal length are determined for the complete graphs, thus solving a problem stated at the end of [6].     

Small cycle double covers of 4-connected planar graphs

Acycle double cover of a graph,G, is a collection of cycles,C, such that every edge ofG lies in precisely two cycles ofC. TheSmall Cycle Double Cover Conjecture, proposed by J. A. Bondy, asserts that every simple bridgeless graph onn vertices has a cycle double cover with at mostn–1 cycles, and is a strengthening of the well-knownCycle Double Cover Conjecture. In this paper, we prove Bondy's conjecture for 4-connected planar graphs.     

Subgraphs as circuits and bases of matroids

As is well known, the cycles of any given graph G may be regarded as the circuits of a matroid defined on the edge set of G. The question of whether other families of connected graphs exist such that, given any graph G, the subgraphs of G isomorphic to some member of the family may be regarded as the circuits of a matroid defined on the edge set of G led us, in two other papers, to the proof of some results concerning properties of the cycles when regarded as circuits of such matroids. Here we prove that the wheels share many of these properties with the cycles. Moreover, properties of subgraphs which may be regarded as bases of such matroids are also investigated.     

A travelling salesman approach to solve the F/no-idle/Cmax problem

This paper investigates the F/no-idle/C_max problem, where machines work continuously without idle time intervals. The idle characteristic is a very strong constraint and it affects seriously the value of C_max criterion. We treat here only the permutation flow-shop configuration for machine no-idle problems with the objective to minimise the makespan. Based on the idea that this problem can be modelled as a travelling salesman problem, an adaptation of the well-known nearest insertion rule is proposed to solve it. A computational study shows the result quality.     

Acyclic edge coloring of subcubic graphs

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and it is denoted by a^′(G). From a result of Burnstein it follows that all subcubic graphs are acyclically edge colorable using five colors. This result is tight since there are 3-regular graphs which require five colors. In this paper we prove that any non-regular connected graph of maximum degree 3 is acyclically edge colorable using at most four colors. This result is tight since all edge maximal non-regular connected graphs of maximum degree 3 require four colors.     

On the structure of the monotone asymmetric travelling salesman polytope I: hypohamiltonian facets

The monotone asymmetric travelling salesman polytope P?ⁿ_T is defined to be the convex hull of the incidence vectors of all hamiltonian circuits and all subsets of these in a complete diagraph of order n. We prove that certain hypohamiltonian diagraphs G=(V,E), i.e. diagraphs which are not hamiltonian but such that G–υ is hamiltonian for all υ?V, induce facets x(E)?n–1 of P?ⁿ_T. This result indicates that P?ⁿ_T has very complicated facets and that it is very unlikely that an explicit complete characterization of P?ⁿ_T can ever be given.     

Lengths of cycles in halin graphs

A Halin graph is a plane graph H = T U C, where T is a plane tree with no vertex of degree two and at least one vertex of degree three or more, and C is a cycle connecting the endvertices of T in the cyclic order determined by the embedding of T. We prove that such a graph on n vertices contains cycles of all lengths l, 3 ≤ l n, except, possibly, for one even value m of l. We prove also that if the tree T contains no vertex of degree three then G is pancyclic.     

Drawing c-planar biconnected clustered graphs

In a graph, a cluster is a set of vertices, and two clusters are said to be non-intersecting if they are disjoint or one of them is contained in the other. A clustered graph C consists of a graph G and a set of non-intersecting clusters. In this paper, we assume that C has a compound planar drawing and each cluster induces a biconnected subgraph. Then we show that such a clustered graph admits a drawing in the plane such that (i) edges are drawn as straight-line segments with no edge crossing and (ii) the boundary of the biconnected subgraph induced by each cluster is a convex polygon.     

Partial linear characterizations of the asymmetric travelling salesman polytope

We consider the linear programming formulation of the asymmetric travelling salesman problem. Several new inequalities are stated which yield a sharper characterization in terms of linear inequalities of the travelling salesman polytope, i.e., the convex hull of tours. In fact, some of the new inequalities as well as some of the well-known subtour elimination constraints are indeed facets of the travelling salesman polytope, i.e., belong to the class of inequalities that uniquely characterize the convex hull of tours to an-city problem.     

On removable cycles through every edge

Mader and Jackson independently proved that every 2‐connected simple graph G with minimum degree at least four has a removable cycle, that is, a cycle C such that G/E(C) is 2‐connected. This paper considers the problem of determining when every edge of a 2‐connected graph G, simple or not, can be guaranteed to lie in some removable cycle. The main result establishes that if every deletion of two edges from G remains 2‐connected, then, not only is every edge in a removable cycle but, for every two edges, there are edge‐disjoint removable cycles such that each contains one of the distinguished edges. © 2002 Wiley Periodicals, Inc. J Graph Theory 42: 155–164, 2003     

An upper bound for the competition numbers of graphs

A hole of a graph is an induced cycle of length at least 4. Kim (2005) [2] conjectured that the competition number k(G) is bounded by h(G)+1 for any graph G, where h(G) is the number of holes of G. In Lee et al. [3], it is proved that the conjecture is true for a graph whose holes are mutually edge-disjoint. In Li et al. (2009) [4], it is proved that the conjecture is true for a graph, all of whose holes are independent. In this paper, we prove that Kim’s conjecture is true for a graph G satisfying the following condition: for each hole C of G, there exists an edge which is contained only in C among all induced cycles of G.     

Minimum cycle cover and Chinese postman problems on mixed graphs with bounded tree-width

Let M=(V,E,A) be a mixed graph with vertex set V, edge set E and arc set A. A cycle cover of M is a family C={C₁,…,C_k} of cycles of M such that each edge/arc of M belongs to at least one cycle in C. The weight of C is . The minimum cycle cover problem is the following: given a strongly connected mixed graph M without bridges, find a cycle cover of M with weight as small as possible. The Chinese postman problem is: given a strongly connected mixed graph M, find a minimum length closed walk using all edges and arcs of M. These problems are NP-hard. We show that they can be solved in polynomial time if M has bounded tree-width.     

Compatible path-cycle-decompositions of plane graphs

Sabidussi's Conjecture states that given an Euler trail T in a connected Euler graph, there always exists a cycle decomposition S such that consecutive edges of T belong to different cycles in S. This conjecture has been solved in a generalized form for planar Euler graphs. A similar result for arbitrary planar graphs is the content of this paper.