A successful algorithm for the undirected Hamiltonian path problem

In this paper a polynomial algorithm called the Minram algorithm is presented which finds a Hamiltonian Path in an undirected graph with high frequency of success for graphs up to 1000 nodes. It first reintroduces the concept described in [13] and then explains the algorithm. Computational comparison with the algorithm by Posa [10] is given.It is shown that a Hamiltonian Path is a spanning arborescence with zero ramification index. Given an undirected graph, the Minram algorithm starts by finding a spanning tree which defines a unique spanning arborescence. By suitable pivots it locates a locally minimal value of the ramification index. If this local minima corresponds to zero ramification index then the algorithm is considered to have ended successfully, else a failure is reported.Computational performance of the algorithm on randomly generated Hamiltonian graphs is given. The random graphs used as test problems were generated using the procedure explained in Section 6.1. Comparison with our version of the Posa algorithm which we call Posa-ran algorithm [10] is also made.     

Stability in the Erdős–Gallai Theorem on cycles and paths,II

The Erd?s–Gallai Theorem states that for $k\ge 3$, any $n$-vertex graph with no cycle of length at least $k$ has at most $\frac{1}{2}(k?1)(n?1)$ edges. A stronger version of the Erd?s–Gallai Theorem was given by Kopylov: If $G$ is a 2-connected $n$-vertex graph with no cycle of length at least $k$, then $e\left(G\right)\le max\{h(n,k,2),h(n,k,?\frac{k?1}{2}?)\}$, where $h(n,k,a)?\left(\genfrac{}{}{0ex}{}{k?a}{2}\right)+a(n?k+a)$. Furthermore, Kopylov presented the two possible extremal graphs, one with $h(n,k,2)$ edges and one with $h(n,k,?\frac{k?1}{2}?)$ edges.In this paper, we complete a stability theorem which strengthens Kopylov’s result. In particular, we show that for $k\ge 3$ odd and all $n\ge k$, every $n$-vertex 2-connected graph $G$ with no cycle of length at least $k$ is a subgraph of one of the two extremal graphs or $e\left(G\right)\le max\{h(n,k,3),h(n,k,\frac{k?3}{2})\}$. The upper bound for $e\left(G\right)$ here is tight.     

ECO:a methodology for the enumeration of combinatorial objects

In this Paper, we illustrate a method (called the ECO method) for enumerating some classes of combinatorial objects. The basic idea of this method is the following: by means of an operator that performs a "local expansion" on the objects, we give some recursive constructions of these classes. We use these constructions to deduce some new funtional equations verified by classes' generating functions. By solving the functional equations, we enumerate the combinatorial objects according to various parameters. We show some applications of the method referring to some classical combinatorial objects, such as: trees, paths, polyminoes and permutations     

Bounded edge-connectivity and edge-persistence of Cartesian product of graphs

The bounded edge-connectivity λ_k(G) of a connected graph G with respect to is the minimum number of edges in G whose deletion from G results in a subgraph with diameter larger than k and the edge-persistence D⁺(G) is defined as λ_d(G)(G), where d(G) is the diameter of G. This paper considers the Cartesian product G₁×G₂, shows λ_k1+k2(G₁×G₂)≥λ_k1(G₁)+λ_k2(G₂) for k₁≥2 and k₂≥2, and determines the exact values of D⁺(G) for G=C_n×P_m, C_n×C_m, Q_n×P_m and Q_n×C_m.     

Powers of matrices over an extremal algebra with applications to periodic graphs

Consider the extremal algebra=({},min,+), using + and min instead of addition and multiplication. This extremal algebra has been successfully applied to a lot of scheduling problems. In this paper the behavior of the powers of a matrix over is studied. The main result is a representation of the complete sequence (A ^m ) _m which can be computed within polynomial time complexity. In the second part we apply this result to compute a minimum cost path in a 1-dimensional periodic graph.     

Infinite retrogression in the Eaves—Saigal algorithm

For certain functionsf fromR ⁿ toR ⁿ , the Eaves—Saigal algorithm computes a path inR ⁿ × (0, 1] which converges to a zero off. In this case, it is shown that even whenf is of classC and has a unique zero, the converging path may retrogress infinitely many times.Army Research Office, Durham, Contract No. DAAG-29-78-G-0026; National Science Foundation Grant No. MCS-77-05623.     

Homotopy groups of Hom complexes of graphs

The notion of ×-homotopy from [Anton Dochtermann, Hom complexes and homotopy theory in the category of graphs, European J. Combin., in press] is investigated in the context of the category of pointed graphs. The main result is a long exact sequence that relates the higher homotopy groups of the space Hom_∗(G,H) with the homotopy groups of Hom_∗(G,HI). Here Hom_∗(G,H) is a space which parameterizes pointed graph maps from G to H (a pointed version of the usual Hom complex), and HI is the graph of based paths in H. As a corollary it is shown that πi(Hom_∗(G,H))≅_×[G,ΩiH], where ΩH is the graph of based closed paths in H and _×[G,K] is the set of ×-homotopy classes of pointed graph maps from G to K. This is similar in spirit to the results of [Eric Babson, Hélène Barcelo, Mark de Longueville, Reinhard Laubenbacher, Homotopy theory of graphs, J. Algebraic Combin. 24 (1) (2006) 31-44], where the authors seek a space whose homotopy groups encode a similarly defined homotopy theory for graphs. The categorical connections to those constructions are discussed.     

Coloring arcs of convex sets

In this note we consider Ramsey-type problems on graphs whose vertices are represented by the vertices of a convex polygon in the Euclidean plane. The edges of the graph are represented by the segments between the points of the polygon. The edges are arbitrarily colored by a fixed number of colors and the problem is to decide whether there exist monochromatic subgraphs of certain types satisfying some geometric conditions. We will give lower and upper bounds for these geometric Ramsey numbers for certain paths and cycles and also some exact values. It turns out that the particular type of the embedding is crucial for the growth rate of the corresponding geometric Ramsey numbers. In particular, the Ramsey numbers for crossing 4-cycles and t colors grow quadratically in t, while for convex 4-cycles they grow at least exponentially.