An upper bound on the length of a Hamiltonian walk of a maximal planar graph

A Hamiltonian walk of a connected graph is a shortest closed walk that passes through every vertex at least once, and the length of a Hamiltonian walk is the total number of edges traversed by the walk. We show that every maximal planar graph with p(≥ 3) vertices has a Hamiltonian cycle or a Hamiltonian walk of length ≤ 3(p - 3)/2.     

Hamiltonian cycles in particular k-partite graphs

Let $\text{G}$(itk, p) denote the class of k-partite graphs, where each part is a stable set of cardinality p and where the edges between any pair of stable sets are those of a perfect matching. Maru?i? has conjectured that if G belongs to $\text{G}$(k, p) and is connected then G is hamiltonian. It is proved that the conjecture is true for k ≤ 3 or p ≤ 3; but for k ≥ 4 and p ≥ 4 a non-hamiltonian connected graph in $\text{G}$(k, p) is constructed.     

Tough graphs and hamiltonian circuits

The toughness of a graph G is defined as the largest real number t such that deletion of any s points from G results in a graph which is either connected or else has at most s/t components. Clearly, every hamiltonian graph is 1-tough. Conversely, we conjecture that for some t₀, every t₀-tough graph is hamiltonian. Since a square of a k-connected graph is always k-tough, a proof of this conjecture with t₀ = 2 would imply Fleischner's theorem (the square of a block is hamiltonian). We construct an infinite family of ($\text{3}\text{2}$)-tough nonhamiltonian graphs.     

On pancyclic digraphs

We show that a strongly connected digraph with n vertices and minimum degree ? n is pancyclic unless it is one of the graphs K_p,p. This generalizes a result of A. Ghouila-Houri. We disprove a conjecture of J. A. Bondy by showing that there exist hamiltonian digraphs with n vertices and $\text{1}\text{2}\text{n(n + 1) – 3}$ edges which are not pancyclic. We show that any hamiltonian digraph with n vertices and at least $\text{1}\text{2}\text{n(n + 1) – 1}$ edges is pancyclic and we give some generalizations of this result. As applications of these results we determine the minimal number of edges required in a digraph to guarantee the existence of a cycle of length k, k ? 2, and we consider the corresponding problem where the digraphs under consideration are assumed to be strongly connected.     

A remark on Hamiltonian cycles

Every 2-connected graph G with $\text{δ ? (v + κ)}\text{3}$ is hamiltonian where v denotes the order, δ the minimum degree and κ the point connectivity of G.     

On n-hamiltonian graphs

A graph G of order p ? 3 is called n-hamiltonian, 0 ? n ? p ? 3, if the removal of any m vertices, 0 ? m ? n, results in a hamiltonian graph. A graph G of order p ? 3 is defined to be n-hamiltonian, ?p ? n ? 1, if there exists ?n or fewer pairwise disjoint paths in G which collectively span G. Various conditions in terms of n and the degrees of the vertices of a graph are shown to be sufficient for the graph to be n-hamiltonian for all possible values of n. It is also shown that if G is a graph of order p ? 3 and $\text{K}\text{(G) ? β(G) + n (?p ? n ? p ? 3)}$, then G is n-hamiltonian.     

Decomposition de Km+Kn en cycles hamiltoniens

Let K_m be the complete graph of order m. We prove that the cartesian sum K_m+K_n can be decomposed into $\text{1}\text{2}$(m+n?2) hamiltonian cycles if m+n is even and into $\text{1}\text{2}$(m+n?3) hamiltonian cycles and a perfect matching if m+n is odd.     

Symmetry groups of some perfect 1-factorizations of complete graphs

The following problem has arisen in the study of graphs, lattices and finite topologies. Is there a 1-factorization of K_2m the complete graph on 2n points, such that the union of every pair of distinct 1-factors is a hamiltonian circuit? In this paper it is noted that on $\text{K}{}_{\mathrm{2m}}\text{1?n?5}$, there is, up to relabelling, only one 1-factorization of the required type. On K₁₂ and whenever there are odd primes p,q>3 such that p + 1 = 2q, there are at least two different such 1-factorizations. These results are obtained by computing symmetry groups. The symmetry groups obtained are Frobenius groups of maximal order (i.e., sharply 2-transitive groups) and direct products of these groups with the group of order 2.     

An extension of Christofides heuristic to the k-person travelling salesman problem

Christofides heuristic is extended to the problem of finding a minimum length k-person tour of a complete graph using lengths that satisfy the triangular inequality. An approachable upper bound of $\text{3}\text{2}$ is demonstrated for the ratio of heuristic to optimum length solutions.     

Sur la structure galoisienne du groupe des unités d'un corps abélien réel de type (p, p)

Let p be a rational prime. We classify those $\text{Z}$[($\text{Z}$/p$\text{Z}$)²]-modules arising as submodules of the units (mod. torsion) of a real abelian field K with Galois group ($\text{Z}$/p$\text{Z}$)², up to isomorphism and up to genus. Explicit results are given when p is 2 or 3. We apply our classification to discuss the existence of a Minkowski unit in K for arbitrary p.     

Darstellung durch definite ternäre quadratische Formen

We study the representation behaviour of a $\text{Z}$-lattice L on a positive definite ternary quadratic space V over $\text{Q}$. As a new tool for this we use the Bruhat-Tits building of the spingroup of the completion of V at a suitable prime p. In Section 2 we show how this can be described in an elementary way as a graph whose vertices are the $\text{Z}$_p-maximal lattices on V_p, and in Section 4 we let this graph induce a graph, whose vertices are lattices on V, which differ from L only at the prime p. In Section 3 we investigate which lattices from the graph defined in Section 2 have a given vector in common. The results are used in Sections 5 and 6 to obtain information on the representation behaviour of some special lattices. In Section 5 we get a list of lattices, which represent all numbers they represent locally everywhere; this list contains that given by Watson in [16]. In Section 6 we sharpen a result of Jones and Pall from [6].     

On finding shortest paths in nonnegative networks

A modification of Dantzig's algorithm for the all pairs shortest paths problem is given. The new algorithm applies only to graphs with nonnegative arc lengths. For an N-node complete graph it has a worst case running time of $\text{2}\text{3}\text{N}{}^3$ triple operations of the form D_ij: = min(D_ij, D_ik + D_kj) and N² log N other comparisons. This contrasts with a lower bound of N(N ? 1) (N ? 2) triples in any pure triple operation algorithm, and seems to be the first algorithm in which no operation need be repeated N³ times. Sparsity and some other conditions may also be utilized.     

On a valence problem in extremal graph theory

Let L ≠ Kinp be a p-chromatic graph and e be an edge of L such that L ? e is (p?1)-chromatic If Gⁿ is a graph of n vertices without containing L but containing K_p, then the minimum valence of Gⁿ is

$\text{?n}\text{1?}\text{1}\text{p?}\text{3}\text{2}\text{+}\text{O}\text{(1).}$

     

An O(n2log n) parallel max-flow algorithm

A synchronized parallel algorithm for finding maximum flow in a directed flow network is presented. Its depth is $\text{O(}\text{n}{}^3\text{(}\text{log}\text{n)}\text{p)}$, where p (p ≤ n) is the number of processors used. This problem seems to be more involved than most of the problems for which efficient parallel algorithms exist. The parallel algorithm induces a new rather simple sequential O(n³) algorithm. This algorithm is very much parallel oriented. It is quite difficult to conceive and analyze it, if one is restricted to the sequential point of view.     

Oscillatory properties of strongly superlinear differential equations with deviating arguments

We regard a graph G as a set {1,…, v} together with a nonempty set E of two-element subsets of {1,…, v}. Let p = (p₁,…, p_v) be an element of $\text{R}$^nv representing v points in $\text{R}$ⁿ and consider the realization G(p) of G in $\text{R}$ⁿ consisting of the line segments [p_i, p_j] in $\text{R}$ⁿ for {i, j} ?E. The figure G(p) is said to be rigid in $\text{R}$ⁿ if every continuous path in $\text{R}$^nv, beginning at p and preserving the edge lengths of G(p), terminates at a point q ? $\text{R}$^nv which is the image (Tp₁,…, Tp_v) of p under an isometry T of $\text{R}$ⁿ. We here study the rigidity and infinitesimal rigidity of graphs, surfaces, and more general structures. A graph theoretic method for determining the rigidity of graphs in $\text{R}$² is discussed, followed by an examination of the rigidity of convex polyhedral surfaces in $\text{R}$³.     

Solution of the Hamiltonian problem for self-complementary graphs

A graph G is said to be highly constricted if there exists a nonempty subset S of vertices such that (i) G ? S has more than |S| components, (ii) S induces the complete graph, and (iii) for every u ∈ S and v ? S, we have d_G(u) > d_G(v), where d_G(u) denotes the degree of u in G. In this paper it is shown that a non-hamiltonian self-complementary graph G of order p is highly constricted, unless p = 4N and G is a particular graph $\text{G}{}^1\text{(4N)}$. It is also proved that if G is a self-complementary graph of order p(≥8) and π its degree sequence, then G is pancyclic if π has a realization with a hamiltonian cycle, and G has a 2-factor if π has a realization with a 2-factor, unless p = 4N and $\text{G = G}{}^1\text{(4N)}$.     

A short note about pursuit games played on a graph with a given genus

On a finite simple graph G = (X,E), p players pursuers $\text{A}{}_1\text{, ∴, A}{}_{\mathrm{p}}$ and one player evader B who move in turn along the edges of G are considered. The p pursuers $\text{A}{}_1\text{, ∴, A}{}_{\mathrm{p}}$ want to catch B who tries to escape. R. Nowakowski and P. Winkler [Discrete Math.43 (1983), 235–240] and A. Quilliot [“Thèse de 3° cycle,” pp. 131–145, Université de Paris VI, 1978] already characterized the graphs such that one pursuer is sufficient to catch the evader B. Very recently, M. Aigner and M. Fromme [Appl. Discrete Math., in press] proved that if G is a planar graph, three pursuers are sufficient to catch the evader B. This result is extended, showing that if G is a graph with a given genus k, then 3 + 2k pursuers are enough to “arrest” the evader B.     

k-Blocks and ultrablocks in graphs

A k-block is a maximal k-vertex-connected subgraph, and a k-block which does not contain a (k + 1)-block is an ultrablock. It is shown that the maximum total number of k-blocks for all k ≥ 1 in any p-vertex graph is [$\text{(2p ? 1)}\text{3}$], and the maximum number of ultrablocks in any p-vertex graph having maximum subgraph connectivity κ? is $\text{[}\text{(p ?}\text{κ}\text{?}\text{+ 1)}\text{2}\text{]}$. In contrast to the linear growth rate of the maximum number of k-blocks in a p-vertex graph, it is shown that the maximum number of critical k-vertex-connected subgraphs of an ultrablock of connectivity k can grow exponentially with p.     

On the first case of Fermat's last theorem

Let p be an odd prime and suppose that for some a, b, c ? $\text{Z}$\p$\text{Z}$ we have that a^p + b^p + c^p = 0. In Part I a simple new expression and a simple proof of the congruences of Mirimanoff which appeared in his papers of 1910 and 1911 are given. As is known, these congruences have Wieferich and Mirimanoff criteria (2^{p ? 1} ≡ 1 mod p² and 3^{p ? 1} ≡ 1 mod p²) as immediate consequences. Mirimanoff's congruences are expressed in the form of polynomial congruences $\text{P}{}_{\mathrm{m}}\text{(}\text{?a}\text{b}\text{) ≡ 0}\text{mod}\text{p}$, 1 ≤ m ≤ p ? 1, and these polynomials P_m(X) are characterized by means of simple relations. In Part II a complement to Kummer-Mirimanoff congruences is given under the hypothesis that p does not divide the second factor of the class number of the p-cyclotomic field.