Search

We show that for all k ≤ − 1 an interval graph is − (k + 1)-Hamilton-connected if and only if its scattering number is at most k. We also give an O(n + m) time algorithm for computing the scattering number of an interval graph with n vertices and m edges, which improves the O(n 3) time bound of Kratsch, Kloks and Muller. As a consequence of our two results the maximum k for which an interval graph is k-Hamilton-connected can be computed in O(n + m) time.

Natural evolution has been manipulating the properties of proteins for billions of years. This ‘design process’ is completely different to conventional human design which assembles well-understood smaller parts in a highly principled way. In evolution-in-materio (EIM), researchers use evolutionary algorithms to define configurations and magnitudes of physical variables (e.g. voltages) which are applied to material systems so that they carry out useful computation. One of the advantages of this is that artificial evolution can exploit physical effects that are either too complex to understand or hitherto unknown. An EU funded project in Unconventional Computation called NASCENCE: Nanoscale Engineering of Novel Computation using Evolution, has the aim to model, understand and exploit the behaviour of evolved configurations of nanosystems (e.g. networks of nanoparticles, carbon nanotubes, liquid crystals) to solve computational problems. The project showed that it is possible to use materials to help find solutions to a number of well-known computational problems (e.g. TSP, Bin-packing, Logic gates, etc.).

A graph G is called homogeneously traceable if for every vertex v of G, G contains a Hamilton path starting from v. For a graph H, we say that G is H-free if G contains no induced subgraph isomorphic to H. For a family H of graphs, G is called H-free if G is H-free for every H∈H. Determining families of graphs H such that every H-free graph G has some graph property has been a popular research topic for several decades, especially for Hamiltonian properties, and more recently for properties related to the existence of graph factors. In this paper we give a complete characterization of all pairs of connected graphs R,S such that every 2-connected {R,S}-free graph is homogeneously traceable.

The Hamiltonian Cycle problem asks if an $n$-vertex graph $G$ has a cycle passing through all vertices of $G$. This problem is a classic $NP$-complete problem. So far, finding an exact algorithm that solves it in $O^*(\aplha^n)$ time for some constant $\alpha

We study parallel knock-out schemes for graphs. These schemes proceed in rounds in each of which each surviving vertex simultaneously eliminates one of its surviving neighbours; a graph is reducible if such a scheme can eliminate every vertex in the graph. We resolve the square-root conjecture, first posed at MFCS 2004, by showing that for a reducible graph $G$, the minimum number of required rounds is $O(\sqrt{n})$; in fact, our result is stronger than the conjecture as we show that the minimum number of required rounds is $O(\sqrt{\alpha})$, where $\alpha$ is the independence number of $G$. This upper bound is tight. We also show that for reducible $K_{1,p}$-free graphs at most $p-1$ rounds are required. It is already known that the problem of whether a given graph is reducible is NP-complete. For claw-free graphs, however, we show that this problem can be solved in polynomial time. We also pinpoint a relationship with (locally bijective) graph homomorphisms.

We continue the study on backbone colorings, a variation on classical vertex colorings that was introduced at WG2003. Given a graph $G = (V,E)$ and a spanning subgraph $H$ of $G$ (the backbone of $G$), a $\lambda$-backbone coloring for $G$ and $H$ is a proper vertex coloring $V\to\{1,2,\ldots\}$ of $G$ in which the colors assigned to adjacent vertices in $H$ differ by at least $\lambda$. The main outcome of earlier studies is that the minimum number $\ell$ of colors for which such colorings $V\to\{1,2,\ldots, \ell\}$ exist in the worst case is a factor times the chromatic number (for all studied types of backbones). We show here that for split graphs and matching or star backbones, $\ell$ is at most a small additive constant (depending on $\lambda$) higher than the chromatic number. Despite the fact that split graphs have a nice structure, these results are difficult to prove. Our proofs combine algorithmic and combinatorial arguments. We also indicate other graph classes for which our results imply better upper bounds on $\ell$ than the previously known bounds.

A well-known formula of Tutte and Berge expresses the size of a maximum matching in a graph $G$ in terms of what is usually called the deficiency of $G$. A subset $X$ of $V(G)$ for which this deficiency is attained is called a Tutte set of $G$. While much is known about maximum matchings, less is known about the structure of Tutte sets. In this article, we study the structural aspects of maximal Tutte sets in a graph $G$. Towards this end, we introduce a related graph $D(G)$. We first show that the maximal Tutte sets in $G$ are precisely the maximal independent sets in its $D$-graph $D(G)$, and then continue with the study of $D$-graphs in their own right, and of iterated $D$-graphs. We show that $G$ is isomorphic to a spanning subgraph of $D(G)$, and characterize the graphs for which $G\cong D(G)$ and for which $D(G)\cong D^2(G)$. Surprisingly, it turns out that for every graph $G$ with a perfect matching, $D^3(G)\cong D^2(G)$. Finally, we characterize bipartite $D$-graphs and comment on the problem of characterizing $D$-graphs in general.

We survey results and open problems related to the toughness of graphs.

Natural Evolution has been exploiting the physical properties of matter since life first appeared on earth. Evolution-in-materio (EIM) attempts to program matter so that computational problems can be solved. The beauty of this approach is that artificial evolution may be able to utilize unknown physical effects to solve computational problems. This methodology is currently being undertaken in a European research project called NASCENCE: Nanoscale Engineering for Novel Computation using Evolution. In this project, a variety of solutions to computational problems have been evolved using mixtures of carbon nanotubes and polymers at room temperature and also with gold nanoparticles at temperatures less than one Kelvin.

The toughness of a (noncomplete) graph G is the minimum value of t for which there is a vertex cut A whose removal yields |A|/t components. Determining toughness is an NP-hard problem for general input graphs. The toughness conjecture of Chvátal, which states that there exists a constant t such that every graph on at least three vertices with toughness at least t is hamiltonian, is still open for general graphs. We extend some known toughness results for split graphs to the more general class of 2K2-free graphs, that is, graphs that do not contain two vertex-disjoint edges as an induced subgraph. We prove that the problem of determining toughness is polynomially solvable and that Chvátal's toughness conjecture is true for 2K2-free graphs.

We consider the existence of several different kinds of factors in 4-connected claw-free graphs. This is motivated by the following two conjectures which are in fact equivalent by a recent result of the third author. Conjecture 1 (Thomassen): Every 4-connected line graph is hamiltonian, i.e., has a connected 2-factor. Conjecture 2 (Matthews and Sumner): Every 4-connected claw-free graph is hamiltonian. We first show that Conjecture 2 is true within the class of hourglass-free graphs, i.e., graphs that do not contain an induced subgraph isomorphic to two triangles meeting in exactly one vertex. Next we show that a weaker form of Conjecture 2 is true, in which the conclusion is replaced by the conclusion that there exists a connected spanning subgraph in which each vertex has degree two or four. Finally we show that Conjectures 1 and 2 are equivalent to seemingly weaker conjectures in which the conclusion is replaced by the conclusion that there exists a spanning subgraph consisting of a bounded number of paths.

A graph is called traceable if it contains a Hamilton path, i.e., a path containing all its vertices. Let G be a graph on n vertices. We say that an induced subgraph of G is o-1-heavy if it contains two nonadjacent vertices which satisfy an Ore-type degree condition for traceability, i.e., with degree sum at least n−1 in G. A block-chain is a graph whose block graph is a path, i.e., it is either a P1, P2, or a 2-connected graph, or a graph with at least one cut vertex and exactly two end-blocks. Obviously, every traceable graph is a block-chain, but the reverse does not hold. In this paper we characterize all the pairs of connected o-1-heavy graphs that guarantee traceability of block-chains. Our main result is a common extension of earlier work on degree sum conditions, forbidden subgraph conditions and heavy subgraph conditions for traceability.

A spanning tree of a connected graph G is said to be an independency tree if all its endvertices are pairwise nonadjacent in G. We prove that a connected graph G has no independency tree if and only if G is a cycle, a complete graph or a complete bipartite graph the color classes of which have equal cardinality.

A graph is HHD-free is it does not contain a house (i.e., the complement of P 5), a hole (a cycle of length at least 5) or a domino (the graph obtained from two 4-cycles by identifying an edge in one C 4 with an edge in the other C 4) as an induced subgraph. The minimum fill-in problem is the problem of finding a chordal supergraph with the smallest possible number of edges. The treewidth problem is the problem of finding a chordal embedding of the graph with the smallest possible clique number. In this note we show that both problems are solvable in polynomial time for HHD-free graphs.

Exact temporal analyses of multi-rate synchronous dataflow (MRSDF) graphs, such as computing the maximum achievable throughput, or sufficient buffer sizes required to reach a minimum throughput, require a homogeneous representation called a homogeneous synchronous dataflow (HSDF) graph. The size of such an HSDF graph may, in the worst case, be exponential in the size of the MRSDF graph. In this paper, we revisit the transformation from MRSDF to HSDF, and show how this transformation may be done either exactly or approximately. The approximate transformation gives both an optimistic and a pessimistic HSDF graph, each of which has the same size as the MRSDF graph. We furthermore show how strict lower and upper bounds on throughput, or on the buffer sizes required to reach a minimum throughput, may be obtained from these approximating graphs.

In this paper the performance gain obtained by combining parallel periodic real-time processes is elaborated. In certain single-core mono-processor configurations, for example embedded control systems in robotics comprising many short processes, process context switches may consume a considerable amount of the available processing power. For this reason it can be advantageous to combine processes, to reduce the number of context switches and thereby increase the performance of the application. As we consider robotic applications only, often consisting of processes with identical periods, release times and deadlines, we restrict these configurations to periodic real-time processes executing on a single-core mono-processor. By graph theoretical concepts and means, we provide necessary and sufficient conditions so that the number of context switches can be reduced by combining synchronising processes.

Let 2P3 denote the disjoint union of two paths on three vertices. A graph G that has no subgraph isomorphic to a graph H is called H-free. The Vertex Coloring problem is the problem to determine the chromatic number of a graph. Its computational complexity for triangle-free H-free graphs has been classified for every fixed graph H on at most 6 vertices except for the case H=2P3. This remaining case is posed as an open problem by Dabrowski, Lozin, Raman and Ries. We solve their open problem by showing polynomial-time solvability.

We give tight algorithmic lower and upper bounds for some double-parameterized subgraph problems when the clique-width of the input graph is one of the parameters. Let G be an arbitrary input graph on n vertices with clique-width at most w. We prove the following results. The Dense (Sparse) k -Subgraph problem, which asks whether there exists an induced subgraph of G with k vertices and at least q edges (at most q edges, respectively), can be solved in time k O(w)·n, but it cannot be solved in time 2 o(wlogk)·n O(1) unless the Exponential Time Hypothesis (ETH) fails. The d -Regular Induced Subgraph problem, which asks whether there exists a d-regular induced subgraph of G, and the Minimum Subgraph of Minimum Degree at least d problem, which asks whether there exists a subgraph of G with k vertices and minimum degree at least d, can be solved in time d O(w)·n, but they cannot be solved in time 2 o(wlogd)·n O(1) unless ETH fails.

Given an undirected graph G = (V, E) with a capacity function w : E → Z+ on the edges, the sparsest cut problem is to find a vertex subset S ⊂ V minimizing Σe∈E(S, V\S) w(e)/(|S||V\S|). This problem is NP-hard. The proof can be found in [16]. In the case of unit capacities (i. e. if w(e) = 1 for every e ∈ E) the problem is to minimize |E(S, V\S)|/(|S||V \ S|) over all subsets S ⊂ V. While this variant of the sparsest cut problem is often assumed to be NP-hard, this note contains the first proof of this fact. We also prove that the problem is polynomially solvable for graphs of bounded treewidth.

We prove that all 3-connected 4-regular planar graphs can be generated from the Octahedron Graph, using three operations. We generated these graphs up to 15 vertices inclusive. Moreover, by including a fourth operation we obtain an alternative to a procedure by Lehel to generate all connected 4-regular planar graphs from the Octahedron Graph.

We prove three complexity results on vertex coloring problems restricted to $P_k$-free graphs, i.e., graphs that do not contain a path on $k$ vertices as an induced subgraph. First of all, we show that the pre-coloring extension version of 5-coloring remains NP-complete when restricted to $P_6$-ree graphs. Recent results of Hoàng et al. imply that this problem is polynomially solvable on $P_5$-free graphs. Secondly, we show that the pre-coloring extension version of 3-coloring is polynomially solvable for $P_6$-free graphs. This implies a simpler algorithm for checking the 3-colorability of $P_6$-free graphs than the algorithm given by Randerath and Schiermeyer. Finally, we prove that 6-coloring is NP-complete for $P_7$-free graphs. This problem was known to be polynomially solvable for $P_5$-free graphs and NP-complete for $P_8$-free graphs, so there remains one open case.

We study parallel knock-out schemes for graphs. These schemes proceed in rounds in each of which each surviving vertex simultaneously eliminates one of its surviving neighbours; a graph is reducible if such a scheme can eliminate every vertex in the graph. We show that, for a reducible graph $G$, the minimum number of required rounds is $O(\sqrt{\alpha}$, where $\alpha$ is the independence number of $G$. This upper bound is tight and the result implies the square-root conjecture which was first posed in MFCS 2004. We also show that for reducible $K_{1,p}$-free graphs at most $p - 1$ rounds are required. It is already known that the problem of whether a given graph is reducible is NP-complete. For claw-free graphs, however, we show that this problem can be solved in polynomial time.

This paper introduces a method which can be used to map applications written in a high level source language program, like C, to a coarse grain reconfigurable architecture, MONTIUM. The source code is first translated into a control dataflow graph. Then after applying graph clustering, scheduling and allocation on this control dataflow graph, it can be mapped onto the target architecture. The clustering and allocation algorithm are presented in detail. High performance and low power consumption are achieved by exploiting maximum parallelism and locality of reference respectively. Using our mapping method, the flexibility of the MONTIUM architecture can be exploited.

In dit artikel wordt een beschrijving gegeven van een masterclass voor leerlingen van 5 vwo die aan de Universiteit Twentewerd georganiseerd. Het doel was om wiskunde onder de aandacht te brengen, met name de toepassingen van wiskunde en wiskunde als onderwerp voor het profielwerkstuk, en hiermee iets te doen aan het imago van wiskunde. De auteurs, die beiden in deeltijd werkzaam zijn aan de Universiteit Twente, zijn betrokken geweest bij de organisatie en dagelijkse begeleiding van deze masterclass.

This paper describes the implementation and evaluation of an algorithm that maps a number of communicating processes to a heterogeneous tiled System on Chip (SoC) architecture at run-time. The mapping algorithm minimizes the total amount of energy consumption, while still providing an adequate Quality of Service (QoS). The properties of the algorithmare described and evaluated and a realistic mapping example is given.

For two given graphs $F$ and $H$, the Ramsey number $R(F,H)$ is the smallest positive integer $p$ such that for every graph $G$ on $p$ vertices the following holds: either $G$ contains $F$ as a subgraph or the complement of $G$ contains $H$ as a subgraph. In this paper, we study the Ramsey numbers $R(P_n,\hat{K}_m)$, where $P_n$ is a path on $n$ vertices and $\hat{K}_m$ is the graph obtained from the join of $K_{1}$ and $P_{m}$. We determine the exact values of $R(P_n,\hat{K}_m)$ for the following values of $n$ and $m$: $1\leq n\leq 5$ and $m\geq 3$; $n\geq 6$ and ($m$ is odd, $3\leq m\leq 2n-1$) or ($m$ is even, $4\leq m\leq n+1$); $6\le n\le7$ and $m=2n-2$ or $m\geq 2n$; $n\geq8$ and $m=2n-2$ or $m=2n$ or $(q\cdot n-2q+1\leq m\leq q\cdot n-q+2$ with $3\leq q\leq n-5)$ or $m\geq (n-3)^2$; odd $n\geq9$ and $(q\cdot n-3q+1\leq m\leq q\cdot n-2q$ with $3\leq q\leq (n-3)/2)$ or $(q\cdot n-q-n+4\leq m\leq q\cdot n-2q$ with $(n-1)/2\leq q\leq n-4)$. Moreover, we give lower bounds and upper bounds for $R(P_{n},\hat{K}_m)$ for the other values of $m$ and $n$.

For two given graphs $F$ and $H$, the Ramsey number $R(F,H)$ is the smallest positive integer $p$ such that for every graph $G$ on $p$ vertices the following holds: either $G$ contains $F$ as a subgraph or the complement of $G$ contains $H$ as a subgraph. In this paper, we study the Ramsey numbers $R(P_{n},W_{m})$, where $P_{n}$ is a path on $n$ vertices and $W_{m}$ is the graph obtained from a cycle on $m$ vertices by adding a new vertex and edges joining it to all the vertices of the cycle. We present the exact values of $R(P_{n},W_{m})$ for the following values of $n$ and $m$: $n=1,2,3$ or $5$ and $m\geq 3$; $n=4$ and $m=3,4,5$ or $7$; $n\geq 6$ and ($m$ is odd, $3\leq m\leq 2n-1$) or ($m$ is even, $4\leq m\leq n+1$); odd $n\ge7$ and $m=2n-2$ or $m=2n$ or $m\geq (n-3)^2$; odd $n\geq 9$ and $q\cdot n-2q+1\leq m\leq q\cdot n-q+2$ with $3\leq q\leq n-5$. Moreover, we give nontrivial lower bounds and upper bounds for $R(P_{n},W_{m})$ for the other values of $m$ and $n$.

The availability of high-level design entry tooling is crucial for the viability of any reconfigurable SoC architecture. This paper presents a template generation method to extract functional equivalent structures, i.e. templates, from a control data flow graph. By inspecting the graph the algorithm generates all the possible templates and the corresponding matches. Using unique serial numbers and circle numbers the algorithm can find all distinct templates with multiple outputs. The template selection algorithm shows how this information can be used in compilers for reconfigurable systems. The objective of the template selection algorithm is to find an efficient cover for an application graph with a minimal number of distinct templates and minimal number of matches.

For two given graphs G and H, the Ramsey number R(G,H) is the smallest positive integer p such that for every graph F on p vertices the following holds: either F contains G as a subgraph or the complement of F contains H as a subgraph. In this paper, we study the Ramsey numbers R(Pn,Fm), where Pn is a path on n vertices and Fm is the graph obtained from m disjoint triangles by identifying precisely one vertex of every triangle (Fm is the join of K1 and mK2). We determine exact values for R(Pn,Fm) for the following values of n and m: n = 1,2 or 3 and m ≥ 2; n ≥ 4 and 2 ≤ m ≤ (n + 1)/2; n ≥ 7 and m = n − 1 or m = n; n ≥ 8 and (k · n − 2k + 1)/2 ≤ m ≤ (k · n − k + 2)/2 with 3 ≤ k ≤ n − 5; n = 4,5 or 6 and m ≥ n − 1; n ≥ 7 and m ≥ (n − 3)2/2.

For two given graphs $G$ and $H$, the Ramsey number $R(G,H)$ is the smallest positive integer $p$ such that for every graph $F$ on $p$ vertices the following holds: either $F$ contains $G$ as a subgraph or the complement of $F$ contains $H$ as a subgraph. In this paper, we study the Ramsey numbers $R(P_{n},F_{m})$, where $P_{n}$ is a path on $n$ vertices and $F_{m}$ is the graph obtained from $m$ disjoint triangles by identifying precisely one vertex of every triangle ($F_{m}$ is the join of $K_{1}$ and $mK_{2}$). We determine exact values for $R(P_{n},F_{m})$ for the following values of $n$ and $m$: $n=1,2$ or $3$ and $m\geq 2$; $n\geq 4$ and $2\leq m\leq (n+1)/2$; $n\geq7$ and $m=n-1$ or $m=n$; $n\geq 8$ and $(k\cdot n-2k+1)/2\leq m\leq (k\cdot n-k+2)/2$ with $3\leq k\leq n-5$; $n=4,5$ or $6$ and $m\geq n-1$; $n\geq 7$ and $m\geq (n-3)^2/2$. We conjecture that $R(P_{n},F_{m}) \leq 2m+n-3$ for the other values of $m$ and $n$.

We prove a lower bound ρ ≥ 9.001 for the i competitive ratio of the so-called online matching problem on a line. As a consequence, the online matching problem is revealed to be strictly more difficult than the “cow problem”.

We study backbone colorings, a variation on classical vertex colorings: Given a graph G=(V,E) and a spanning subgraph H (the backbone) of G, a backbone coloring for G and H is a proper vertex coloring V →{ 1,2,... } in which the colors assigned to adjacent vertices in H differ by at least two. We concentrate on the cases where the backbone is either a spanning tree or a spanning path. For tree backbones of G, the number of colors needed for a backbone coloring of G can roughly differ by a multiplicative factor of at most 2 from the chromatic number χ(G); for path backbones this factor is roughly 32 . In the special case of split graphs G, the difference from χ(G) is at most an additive constant 2 or 1, for tree backbones and path backbones, respectively. The computational complexity of the problem ‘Given a graph G, a spanning tree T of G, and an integer l, is there a backbone coloring for G and T with at most l colors?’ jumps from polynomial to NP-complete between l = 4 (easy for all spanning trees) and l = 5 (difficult even for spanning paths).

An energy-efficient architecture is vital for the next generation of mobile phones. The battery operated nature of these systems requires them to be designed and operated in a highly energy-efficient manner to maximize the battery lifetime. In this paper the characteristics (in terms of power consumption and quality) of a RAKE receiver in combination with a turbo decoder are considered. Important parameters are selected and their influences on the energy consumption and quality are investigated by means of simulations.

A subcoloring is a vertex coloring of a graph in which every color class induces a disjoint union of cliques. We derive a number of results on the combinatorics, the algorithmics, and the complexity of subcolorings. On the negative side, we prove that 2-subcoloring is NP-hard for comparability graphs, and that 3-subcoloring is NP-hard for AT-free graphs and for complements of planar graphs. On the positive side, we derive polynomial time algorithms for 2-subcoloring of complements of planar graphs, and for r-subcoloring of interval and of permutation graphs. Moreover, we prove asymptotically best possible upper bounds on the subchromatic number of interval graphs, chordal graphs, and permutation graphs in terms of the number of vertices.

A subcoloring is a vertex coloring of a graph in which every color class induces a disjoint union of cliques. We derive a number of results on the combinatorics, the algorithmics, and the complexity of subcolorings.

Given an undirected graph whose nodes are partitioned into a number of clusters, the Generalized Minimum Spanning Tree problem (denoted GMSTP) is then to find a minimum-cost tree which includes exactly one node from each cluster. We present several integer programming formulations of the problem and compare the polyhedra defined by the LP relaxations of these formulations. Based on a new formulation of the GMSTP we give an heuristic solution, a lower bound procedure and discuss the advantages of our approach in comparison with an erlier method.

We consider the degree-preserving spanning tree (DPST) problem: Given a connected graph G, find a spanning tree T of G such that as many vertices of T as possible have the same degree in T as in G. This problem is a graph-theoretical translation of a problem arising in the system-theoretical context of identifiability in networks, a concept which has applications in, for example, water distribution networks and electrical networks. We show that the DPST problem is NP-complete, even when restricted to split graphs or bipartite planar graphs, but that it can be solved in polynomial time for graphs with a bounded asteroidal number and for graphs with a bounded treewidth. For the class of interval graphs, we give a linear time algorithm. For the class of cocomparability graphs, we give an O(n4) algorithm. Furthermore, we present linear time approximation algorithms for planar graphs of a worst-case performance ratio of 1 - e for every e > 0.

We now know that not every $2$-tough graph is hamiltonian. In fact for every $\epsilon > 0$, there exists a ($9/4 - \epsilon$) - tough nontraceable graph. We continue our quadrennial survey of results that relate the toughness of a graph to its cycle structure.

We give a strengthening of the closure concept for claw-free graphs introduced by the second author in 1997. The new closure of a claw-free graph $G$ defined here is uniquely determined and preserves the value of the circumference of $G$. We present an infinite family of graphs with $n$ vertices and $3n/2 -1$ edges for which the new closure is the complete graph $K_n$

A graph is distance hereditary if it preserves distances in all its connected induced subgraphs. The MINIMUM FILL-IN problem is the problem of finding a chordal supergraph with the smallest possible number of edges. The TREEWIDTH problem is the problem of finding a chordal embedding of the graph with the smallest possible clique number. In this paper we show that both problems are solvable in linear time for distance hereditary graphs.

A number of results in Hamiltonian graph theory are of the form $\mathcal{P}$$_{1}$ implies $\mathcal{P}$$_{2}$, where $\mathcal{P}$$_{1}$ is a property of graphs that is NP-hard and $\mathcal{P}$$_{2}$ is a cycle structure property of graphs that is also NP-hard. Such a theorem is the well-known Chv\'{a}tal-Erd\"{o}s Theorem, which states that every graph $G$ with $\alpha \leq \kappa $ is Hamiltonian. Here $\kappa $ is the vertex connectivity of $G$ and $\alpha $ is the cardinality of a largest set of independent vertices of $G$. In another paper Chv\'{a}tal points out that the proof of this result is in fact a polynomial time construction that either produces a Hamilton cycle or a set of more than $\kappa $ independent vertices. In this note we point out that other theorems in Hamiltonian graph theory have a similar character. In particular, we present a constructive proof of the well-known theorem of Jung for graphs on $16$ or more vertices..

We consider the existence of several different kinds of factors in 4-connected claw-free graphs. This is motivated by the following two conjectures which are in fact equivalent by a recent result of the third author. Conjecture 1 (Thomassen): Every 4-connected line graph is Hamiltonian, i.e. has a connected 2-factor. Conjecture 2 (Matthews and Sumner): Every 4-connected claw-free graph is hamiltonian. We first show that Conjecture 2 is true within the class of hourglass-free graphs, i.e. graphs that do not contain an induced subgraph isomorphic to two triangles meeting in exactly one vertex. Next we show that a weaker form of Conjecture 2 is true, in which the conclusion is replaced by the conclusion that there exists a connected spanning subgraph in which each vertex has degree two or four. Finally we show that Conjecture 1 and 2 are equivalent to seemingly weaker conjectures in which the conclusion is replaced by the conclusion that there exists a spanning subgraph consisting of a bounded number of paths.