Bermond conjectured that if G is Hamilton cycle decomposable, then L(G), the line graph of G, is Hamilton cycle decomposable. In this paper, we construct a perfect set of Euler tours for the complete tripartite graph Kp,p,p for any prime p and hence prove Bermond’s conjecture for G = Kp,p,p.

For the Traveling Salesman Problem (TSP) on Halin graphs with three types of cost functions: sum, bottleneck and balanced and with arbitrary real edge costs we compute in polynomial time the persistency partition $E_{All}$, $E_{Some}$, $E_{None}$ of the edge set E, where: $E_{All}$ = e ∈ E, e belongs to all optimum solutions, $E_{None}$ = e ∈ E, e does not belong to any optimum solution and $E_{Some}$ = e ∈ E, e belongs to some but not to all optimum solutions.

In [1], Brousek characterizes all triples of connected graphs, G₁,G₂,G₃, with $G_i=K_{1,3}$ for some i = 1,2, or 3, such that all G₁G₂ G₃-free graphs contain a hamiltonian cycle. In [8], Faudree, Gould, Jacobson and Lesniak consider the problem of finding triples of graphs G₁,G₂,G₃, none of which is a $K_{1,s}$, s ≥ 3 such that G₁G₂G₃-free graphs of sufficiently large order contain a hamiltonian cycle. In [6], a characterization was given of all triples G₁,G₂,G₃ with none being $K_{1,3}$, such that all G₁G₂G₃-free graphs are...

For each fixed pair α,c > 0 let INDEPENDENT SET ($m\le c{n}^{\alpha }$) and INDEPENDENT SET ($m\ge \left(ⁿ₂\right)-c{n}^{\alpha }$) be the problem INDEPENDENT SET restricted to graphs on n vertices with $m\le c{n}^{\alpha }$ or $m\ge \left(ⁿ₂\right)-c{n}^{\alpha }$ edges, respectively. Analogously, HAMILTONIAN CIRCUIT ($m\le n+c{n}^{\alpha }$) and HAMILTONIAN PATH ($m\le n+c{n}^{\alpha }$) are the problems HAMILTONIAN CIRCUIT and HAMILTONIAN PATH restricted to graphs with $m\le n+c{n}^{\alpha }$ edges. For each ϵ > 0 let HAMILTONIAN CIRCUIT (m ≥ (1 - ϵ)(ⁿ₂)) and HAMILTONIAN PATH (m ≥ (1 - ϵ)(ⁿ₂)) be the problems HAMILTONIAN CIRCUIT and HAMILTONIAN PATH restricted...