✦ LIBER ✦

Computation of the 0-dual closure for hamiltonian graphs

✍ Scribed by Ingo Schiermeyer

Publisher: Elsevier Science
Year: 1993
Tongue: English
Weight: 601 KB
Volume: 111
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(93)90183-t

No coin nor oath required. For personal study only.

✦ Synopsis

Schiermeyer, I., Computation of the O-dual closure for hamiltonian graphs, Discrete Mathematics 111 (1993) 455-464. The well-known closure concept of Bondy and Chvbtal (1976) is based on degree sums of pairs of nonadjacent vertices. It generalizes six earlier sufficient degree conditions for hamiltonian graphs Ainouche and Christofides (1987) introduced a more general concept which is called the O-dual closure. We prove that this concept generalizes five sufficient conditions for hamiltonian graphs which are not generalized by the concept of Bondy and Chvatal(1976).

📜 SIMILAR VOLUMES

On the computational complexity of graph

On the computational complexity of graph closures

✍ Angelo Monti 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 375 KB

Computable Riesz representation for the

Computable Riesz representation for the dual of C [0; 1]

✍ Hong Lu; Klaus Weihrauch 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 308 KB

## Abstract By the Riesz representation theorem for the dual of __C__ [0; 1], if __F__: __C__ [0; 1] → ℝ is a continuous linear operator, then there is a function __g__: [0;1] → ℝ of bounded variation such that __F__ (__f__) = ∫ __f__ d__g__ (__f__ ∈ __C__ [0; 1]). The function __g__ can be normali

Closure for the property of having a ham

Closure for the property of having a hamiltonian prism

✍ Daniel Král; Ladislav Stacho 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 252 KB

## Abstract We prove that a graph __G__ of order __n__ has a hamiltonian prism if and only if the graph Cl~4__n__/3–4/3~(__G__) has a hamiltonian prism where Cl~4__n__/3–4/3~(__G__) is the graph obtained from __G__ by sequential adding edges between non‐adjacent vertices whose degree sum is at leas

A simple upper bound for the hamiltonian

A simple upper bound for the hamiltonian index of a graph

✍ Marko Lovrečič Saražin 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 466 KB

Parallel algorithm for the computation o

Parallel algorithm for the computation of characteristic polynomials of chemical graphs

✍ P. Venuvanalingam; P. Thangavel 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 413 KB

A parallel algorithm is developed for the f i t time based on Frame's method to compute the characteristic polynomials of chemical graphs. This algorithm can handle all types of graphs: ordinary, weighted, directed, and signed. Our algorithm takes only linear time in the CRCW PRAM model with O(n9) p

Limit distribution for the existence of

Limit distribution for the existence of hamiltonian cycles in a random graph

✍ János Komlós; Endre Szemerédi 📂 Article 📅 1983 🏛 Elsevier Science 🌐 English ⚖ 874 KB

P&a proved that a random graph with clt log n edges is Hamiltonian with probability tending to 1 if c >3. Korsunov improved this by showing that, if Gn is a random graph with \*n log n + in log log n + f(n)n edges and f(n) --\*m, then G" is Hamiltonian, with probability tending to 1. We shall prove