Printer Friendly

Progress on the Traceability Conjecture for Oriented Graphs.

1 Introduction

The set of vertices and the set of arcs of a digraph D are denoted by V(D) and A(D), respectively, and the order of D is denoted n(D). A directed cycle (path, walk) in a digraph will simply be called a cycle (path, walk). A digraph is hamiltonian if it contains a cycle that visits every vertex, traceable if it contains a path that visits every vertex, walkable (or unilaterally connected) if it contains a walk that visits every vertex, and strong (or strongly connected) if it has a closed walk that visits every vertex.

The maximum number of vertices on a path in a digraph D is denoted by [lambda] (D). A digraph D of order n is p-deficient if [lambda] (D) = n - p.

A maximal strong subdigraph of a digraph D is called a strong component of D. We say that a strong component is trivial if has only one vertex.

If v is a vertex of a digraph D, we denote the sets of out-neighbours and in-neighbours of v by [N.sup.+](v) and [N.sup.-](v) and the cardinalities of these sets by [d.sup.+](v) and [d.sup.-](v), respectively. The minimum degree of D, [delta](D), is defined as [min.sub.v[member of]V] ([d.sup.+](v) + [d.sup.-](v)).

If D is a digraph and X [union] V(D), then (X) denotes the subdigraph induced by X in D.

A digraph of order n is k-traceable for some k < n if each of its induced subdigraphs of order k is traceable. The main topic of this paper is the following conjecture, which was formulated by Morten Nielsen in 2006. It is stated in (5).

Conjecture 1.1 (The Traceability Conjecture (TC)) For k [greater than or equal to] 2, every k-traceable oriented graph of order at least 2k - 1 is traceable.

The Traceability Conjecture was inspired by the Path Partition Conjecture for 1-deficient Oriented Graphs (called the OPPC(1)), which is treated in (5) and (10). The OPPC(1) is an important special case of the Path Partition Conjecture for Digraphs (DPPC), which is treated in (2) and (4). The OPPC(1) may be stated as follows in terms of traceability (see (5)).

Conjecture 1.2 (OPPC(1)) Let a and b be integers with 1 [less than or equal to] a [less than or equal to] b. If D is a 1-deficient oriented graph of order n = a + b + 1, then D is not (a + 1)-traceable or D is not (b + 1)-traceable.

The truth of the TC would obviously imply the truth of the OPPC(1). In particular, if the TC holds for k = t, it would follow that the OPPC(1) holds for a = t - 1.

In the case of undirected graphs, it is an easy corollary of Dirac's degree condition for hamiltonicity that for k [greater than or equal to] 2 every k-traceable graph of order at least 2k - 1 is hamiltonian. The same is not true for oriented graphs, though we do have the following result, which is proved in (5).

Theorem 1.3 For k = 2, 3 or 4, every strong k-traceable oriented graph of order greater than k is hamiltonian.

For k [greater than or equal to] 5 the situation changes dramatically. As shown in (5), for every n [greater than or equal to] 5 there exists a nonhamiltonian strong oriented graph of order n that is k-traceable for every k [member of] {15,...,n}. However, no counterexample to the TC has yet been found. In fact, we do not even know if there exists a k-traceable oriented graph of order bigger than k + 1 that is nontraceable.

It is shown in (5) that the TC holds for k [less than or equal to] 5. In this paper we prove that the TC also holds for k = 6, i.e. every 6-traceable oriented graph of order at least 11 is traceable.

2 Auxiliary Results

First, we present some general properties of k-traceable oriented graphs. The following result concerning the minimum degree is proved in (5).

Lemma 2.1 If k [greater than or equal to] 2 and D is a k-traceable oriented graph of order n [greater than or equal to] k, then [delta](D) [greater than or equal to] n - k + 1.

Our next result concerns k-traceable oriented graphs that are nontraceable.

Lemma 2.2 Suppose D is a k-traceable oriented graph of order n > k. If D is nontraceable and v is a vertex of D with [d.sup.+](v) = n - k + 1 then ([N.sup.+](v)) is nontraceable. Similarly, if [d.sup.-](v) = n - k + 1, then ([N.sup.-](v)) is nontraceable.

Proof: Suppose ([N.sup.+](v)) has a hamiltonian path [x.sub.1][x.sub.2]...[x.sub.n - k + 1]. Then the graph D - [x.sub.1],....[x.sub.n - k]} has order k and therefore has a hamiltonian path P. If P contains the arc [vx.sub.n - k + 1], then the path obtained from P by replacing the arc [vx.sub.n - k + 1] with the path [vx.sub.1][x.sub.2]...[x.sub.n - k][x.sub.n - k + 1] is a hamiltonian path of D. If P does not contain the arc [vx.sub.n - k + 1], then v is the end-vertex of P. In this case P[x.sub.1][x.sub.2]...[x.sub.n - k] is a hamiltonian path of D. The proof that ([N.sup.-](v)) is nontraceable if [d.sup.-](v) = n - k + 1 is similar.

The following easy observation is proved in (5).

Lemma 2.3 If D is an oriented graph of order n that is k-traceable for some k [member of] {2,..., n}, then D is walkable.

In view of Lemma R7 we shall be mainly concerned with walkable oriented graphs. The strong components of a digraph have an acyclic ordering, i.e. they may be labelled [D.sub.1],...,[D.sub.h] such that if there is an arc from [D.sub.i] to [D.sub.j], then i [less than or equal to] j (cf. (1), p. 17). If D is walkable then, for i = 1,...,h - 1 there is at least one arc from [D.sub.i] to [D.sub.i + 1], so in this case the acyclic ordering is unique. Throughout the paper we shall label the strong components of a walkable oriented graph in accordance with this unique acyclic ordering.

In the proof of our main result we shall consider oriented graphs that are strong and those that are not strong (but walkable) separately. The nonstrong case relies on the following three results concerning the strong components of k-traceable oriented graphs. The first is an obvious but useful result, proved in (5).

Lemma 2.4 If P is a path in a digraph D, then the intersection of P with any strong component of D is either empty or a path.

The next result follows from Theorem (c)and Lemma FM

Lemma 2.5 Let k [greater than or equal to] 5 and suppose D is a k-traceable oriented graph of order n > k. Then every nonhamiltonian nontrivial strong component of D has order at least n - k + 5.

Proof: Suppose D has a nonhamiltonian nontrivial strong component X of order at most n - (k - 4). Then |V(X)| [greater than or equal to] 4 and |V(D) \ V(X)| [greater than or equal to] k - 4. If |V(X)| = 4, then |V(D) \ V(X)| = n - 4 [greater than or equal to] k - 3. Theorem 1.3 implies that X is not 3-traceable and, if |V(X)| > 4, then X is also not 4-traceable. In either case, we can choose an induced subdigraph H of D of order k such that (V (H) [intersection] V (X)) is nontraceable. But then it follows from Lemma 2.4 that H is nontraceable, contradicting our assumption that D is k-traceable.

The following result, which is proved in (5), is very useful in the case of k-traceable oriented graphs of large enough order.

Lemma 2.6 Suppose D is a k-traceable oriented graph of order at least 2k - 1, k [greater than or equal to] 2. If D is nontraceable, then D has a nonhamiltonian nontrivial strong component.

For the proof of the strong case of our main result, we shall use the following theorem, proved in (3).

Theorem 2.7 (Chen and Manalastas) Every nontraceable strong digraph has independence number at least 3.

We shall also use the following result on k-traceable strong oriented graphs, which appears as part of the proof of Theorem 3.5 in (5).

Lemma 2.8 Let D be a k-traceable strong oriented graph and let X = {[x.sub.1], [x.sub.2], [x.sub.3]} be an independent set of vertices in D. Let

[A.sub.i] = V(D) \ {X [union] [N.sup.-]([x.sub.i])}, [B.sub.i] = V(D) \ {X [union] [N.sup.+]([x.sub.i])}, i = 1,2,3.

Then |[A.sub.i] [less than or equal to] 3k - 12 and |[B.sub.i] [less than or equal to] 3k - 12 for i = 1,2,3.

Proof: Let i, j be any pair of distinct integers in {1, 2, 3}. If |[A.sub.i] [intersection] [A.sub.j]| [greater than or equal to] k - 3, let H be an induced subdigraph of D whose vertex set consists of [x.sub.1], [x.sub.2], [x.sub.3] and k - 3 vertices of [A.sub.i] [intersection] [A.sub.j]. Then H has order k and is nontraceable, since both [x.sub.i] and [x.sub.j] have no in-neighbours in H. This contradiction shows that |[A.sub.i] [intersection] [A.sub.j]| [less than or equal to] k - 4. Similarly, |[B.sub.i] [intersection] [B.sub.j]| [less than or equal to] k - 4. Now suppose |[A.sub.1] [intersection] [B.sub.2]| [greater than or equal to] 2k - 7. Then, since |[A.sub.1] [intersection] [A.sub.3]| [less than or equal to] k - 4, at most k - 4 vertices of |[A.sub.1] [intersection] [B.sub.2]| are in [A.sub.3], so at least k - 3 vertices of |[A.sub.1] [intersection] [B.sub.2]| are in [B.sub.3], but then |[B.sub.2] [intersection] [B.sub.3]| [greater than or equal to] k - 3. This contradiction proves that |[A.sub.1] [intersection] [B.sub.2]| [greater than or equal to] 2k - 8. But [A.sub.1] = ([A.sub.1] [intersection] [A.sub.2]) [union] ([A.sub.1] [intersection] [B.sub.2]). Hence |[A.sub.1]| [less than or equal to] (k - 4) + 2k - 8 = 3k -12. Similarly, |[B.sub.1]| < 3k -12.

Theorem 2.7 and Lemma 2.8 were used in (5) to prove the following theorem.

Theorem 2.9 For k [greater than or equal to] 2 every k-traceable strong oriented graph of order at least 6k - 20 is traceable.

We now turn our attention to k-traceable oriented graphs of small order. Knowledge of their structure is actually important when considering the traceability of k-traceable oriented graphs of large order.

3 Hypotraceable oriented graphs

A digraph D of order n is called hypotraceable if n [greater than or equal to] 3 and D is (n - 1)-traceable but not n-traceable. Thus a hypotraceble digraph is nontraceable but the removal of any vertex leaves a traceable digraph. Our next result shows the importance of hypotraceable oriented graphs in connection with the TC.

Lemma 3.1 If k > 2 and D is a nontraceable, k-traceable oriented graph of order n [greater than or equal to] k + 1, then D has a hypotraceable induced subdigraph of order h for some k + 1 < h < n.

Proof: Suppose n = k + r. Then, for any set S consisting of r vertices of D, the oriented graph D - S is traceable. If D itself is not hypotraceable, then D has a vertex [x.sub.1] such that D - [x.sub.1] is nontraceable. We repeat this procedure until we obtain a subset {[x.sub.1],...,[x.sub.t} in D for some t [less than or equal to] r - 1 such that D - {[x.sub.1],...,[x.sub.t]} is hypotraceable.

In view of Lemma 3.1 it is important to know the possible orders of hypotraceable oriented graphs. Grotschel, Thomassen and Wakabayashi constructed an infinite family of hypotraceable oriented graphs in (6). These graphs are obtained from hypohamiltonian digraphs. The smallest hypotraceable oriented graph constructed by applying the construction in (6) to hypohamiltonian digraphs constructed by Thomassen in (9) has order 12. If there does not exist a hypotraceable oriented graph of order less than 12, then it would follow immediately from Theorem 2.9 and Lemma 3.1 that every 6-traceable oriented graph of order n, where 6 [less than or equal to] n [less than or equal to] 12 is traceable. However, the best that we've managed to do so far was to show that there does not exist a hypotraceable oriented graph of order less than 8. To prove this, we need the following result, which is stated in (6) without proof.

Lemma 3.2 If D is a hypotraceable digraph, then D does not have a vertex with in degree 1 or out degree 1.

Proof: Let D be a hypotraceable digraph, x [member of] V(D) and suppose y is the only out-neighbour of x. Then every hamiltonian path of D - {y} must end in x, hence can be extended with y, which is a contradiction.

A strong digraph of order at least 2 cannot have a vertex of indegree 0 or outdegree 0, so the following holds.

Corollary 3.3 If D is a strong hypotraceable digraph, then D has minimum indegree at least 2 and minimum outdegree at least 2.

We shall also use the following corollary of Lemma 2.2.

Corollary 3.4 Let D be a hypotraceable oriented graph. If D contains a vertex v, such that [d.sup.+](v) = 2 (or [d.sup.-](v) = 2), then the out-neighbours (or in-neighbours) of v are nonadjacent.

The following result is proved in (7).

Lemma 3.5 (Grotschel and Wakabayashi) Every nontrivial strong component of a hypotraceable oriented graph has order at least 5.

It is stated in (6) (without proof) that there does not exist a hypotraceable digraph of order less than 7. We now use the lemmas above to extend this bound in the case of oriented graphs.

Lemma 3.6 There does not exist a hypotraceable oriented graph of order less than 8.

Proof: Suppose D is a hypotracable oriented graph of order n, with 3 [less than or equal to] n [less than or equal to] 7.

Case 1. D is strong: In this case Theorem 2.7 implies that D has three independent vertices {[x.sub.1], [x.sub.2], [x.sub.3]} and it follows from Corollary 3.3 that [d.sup.+]([x.sub.1]) [greater than or equal to] 2 and [d.sup.-]([x.sub.1]) [greater than or equal to] 2. This is not possible if n [less than or equal to] 6, so assume n = 7. Then [d.sup.+]([x.sub.i]) = [d.sup.-]([x.sub.i]) = 2 for i = 1, 2, 3. Let [N.sup.+]([x.sub.1]) = {[a.sub.1], [a.sub.2]} and [N.sup.-]([x.sub.1]) = {[b.sub.1], [b.sub.2]}. By Corollary 3.4 {[a.sub.1], [a.sub.2]} and {[b.sub.1], [b.sub.2]} are independent sets. If D - {[b.sub.1], [b.sub.2]} has a hamiltonian path Q, then Q starts at [x.sub.1] and ends at either [x.sub.2] or [x.sub.3], say [x.sub.3]. But [d.sup.+]([x.sub.3]) = 2, so [x.sub.3] is adjacent to at least one of [b.sub.1] and [b.sub.2], say [b.sub.2]. But then [b.sub.1]Q[b.sub.2] is a hamiltonian path of D. This contradiction shows that D - {[b.sub.1], [b.sub.2]} has no hamiltonian path and hence D - [b.sub.1] has no hamiltonian path starting at [b.sub.2]. Since D is 6-traceable, D - [b.sub.1] has a hamiltonian path P. The initial vertex of P cannot be [x.sub.1], otherwise [b.sub.1]P is a hamiltonian path of D. Without loss of generality, we assume that the initial vertex of P is either [x.sub.2] or [a.sub.1].

Subcase 1.1 The initial vertex of P is [x.sub.2]: In this case [b.sub.1] [??] [N.sup.-]([x.sub.2]), otherwise [b.sub.1]P would be a hamiltonian path of D. Hence [b.sub.1] [member of] [N.sup.+]([x.sub.2]). There are now two possibilities to consider for the second vertex of P.

Subcase 1.1.1 The second vertex of P is [a.sub.1]: Then [N.sup.+]([x.sub.2]) = {[a.sub.1], [b.sub.1]}, so [N.sup.- ]([x.sub.2]) = {[a.sub.2], [b.sub.2]}. If [a.sub.1][x.sub.3] [member of] A(D), then [x.sub.1][a.sub.2][x.sub.2][a.sub.1][x.sub.3] is a hamiltonian path in D - {[b.sub.1], [b.sub.2]}, but we have shown D - {[b.sub.1], [b.sub.2]} is nontraceable, so [a.sub.1] [??] [N.sup.-]([x.sub.3]). Also, [a.sub.2] [??] [N.sup.-]([x.sub.3]), otherwise [b.sub.2][x.sub.2][b.sub.1][x.sub.1][a.sub.2][x.sub.3][a.sub.1] would be a hamiltonian path of D. Hence [N.sup.-]([x.sub.3]) = {[b.sub.1], [b.sub.2]}. But then [b.sub.2][x.sub.3][a.sub.2][x.sub.2][b.sub.1][x.sub.1][a.sub.1] is a hamiltonian path of D.

Subcase 1.1.2 The second vertex of P is [b.sub.2]: Then [N.sup.+]([x.sub.2]) = {[b.sub.1], [b.sub.2]}, so [N.sup.-]([x.sub.2]) = {[a.sub.1], [a.sub.2]}. Then we may assume w.l.o.g. that P is the path [x.sub.2][b.sub.2][x.sub.1][a.sub.1][x.sub.3][a.sub.2]. But then [b.sub.2][x.sub.1][a.sub.1][x.sub.3][a.sub.2][x.sub.2][b.sub.1] is a hamiltonian path in D.

Subcase 1.2 The initial vertex of P is [a.sub.1]: We have shown that D - {[b.sub.1], [b.sub.2]} has no hamiltonian path, so we may assume w.l.o.g. that D - [b.sub.1] has the hamiltonian path al[x.sub.2][b.sub.2][x.sub.1][a.sub.2][x.sub.3]. Then [b.sub.1] [??] [N.sup.+]([x.sub.3]), so [N.sup.+]([x.sub.3]) = {[a.sub.1], [b.sub.2]}. But then [b.sub.1][x.sub.3][a.sub.1][x.sub.2][b.sub.2][x.sub.1][a.sub.2] is a hamiltonian path in D.

Case 2. D is not strong:

Subcase 2.1 D has a nontrivial strong component X that is nonhamiltonian: By Lemma 3.5 |V (X)| [greater than or equal to] 5, so n = 6 or 7. Since D is (n - 1)-traceable, Lemma 2.5 now implies that |V (X)| = 6 and hence n = 7. By symmetry, we may assume that [D.sub.1] has order one and X = [D.sub.2]. Let x be the vertex in [D.sub.1] and let [v.sub.1][v.sub.2]...[v.sub.6] be a path in [D.sub.2]. Then x, [v.sub.6] [??] [N.sup.-]([v.sub.1]), so it follows from Lemma 3.2 and Corollary 3.4 that {[v.sub.3], [v.sub.5]} [[subset].bar] [N.sup.-]([v.sub.1]). Similarly, {[v.sub.2], [v.sub.4]} [[subset].bar] [N.sup.+]([v.sub.6]). Hence each of the vertices [v.sub.1], [v.sub.4] and [v.sub.6] is an initial vertex of a hamiltonian path of [D.sub.2], so x is not adjacent to [v.sub.1], [v.sub.4] or [v.sub.6]. However, Lemma 3.2 implies that [d.sup.+](x) [greater than or equal to] 2 and, by Lemma 3.4 [N.sup.+](x) [not equal to] {[v.sub.2], [v.sub.3]}, so [v.sub.5] [member of] [N.sup.+](x). Then [v.sub.6] [??] [N.sup.+]([v.sub.1]), otherwise x[v.sub.5][v.sub.1][v.sub.6][v.sub.2][v.sub.3][v.sub.4] is a hamiltonian path in D. Hence [N.sub.+]([v.sub.1]) = {[v.sub.2], [v.sub.4]}, which implies that [v.sub.2] and [v.sub.4] are nonadjacent vertices. But then [N.sup.+]([v.sub.4]) {[v.sub.5]}, which contradicts Lemma 3. .

Subcase 2.2 Every nontrivial strong component of D is hamiltonian: In this case, if D had only two strong components, D would be traceable. Hence D has at least three strong components. By Lemma each nontrivial strong component of D has order at least 5. Thus the only possibility is that n = 7 and D has two trivial strong components and one of order 5. The two trivial strong components cannot be consecutive, otherwise D would be traceable. Hence n([D.sub.1]) = 1, n([D.sub.2]) = 5 and n([D.sub.3]) = 1.

Let x be the vertex in [D.sub.1], let y be the vertex in [D.sub.3] and let C = [v.sub.1][v.sub.2][v.sub.3][v.sub.4][v.sub.5][v.sub.1] be a hamiltonian cycle of [D.sub.2]. If x has only one out-neighbour [v.sub.1] in [D.sub.2], then D - [v.sub.1] cannot be traceable, so |[N.sup.-], (x) n V ([D.sub.2]) I [greater than or equal to] 2. Similarly, I[N.sup.-](y) n V([D.sub.2])1 [greater than or equal to] 2. Since D is nontraceable, no predecessor of a neighbour of x on C is a neighbour of y. Thus, at least one of x and y has at most two neighbours in [D.sub.2]. By symmetry, we may assume that x has only two out-neighbours in [D.sub.2], say a and b. If ab is an arc in D, then any hamiltonian path xb...[v.sub.j]y of D - a can be extended to a hamiltonian path xab...[v.sub.j] of D. Hence a and b are nonadjacent. We may assume, w.l.o.g. that a = [v.sub.2] and b = [v.sub.5]. Then [v.sub.1], [v.sub.4] [??] [N.sup.-](y). But then [v.sub.1] has only four possible neighbours, namely [v.sub.2], [v.sub.3], [v.sub.4], [v.sub.5]. Hence, by Lemma 3.2 and Corollary 3.4, [N.sup.+]([v.sub.1]) = {[v.sub.2], [v.sub.4]} and [N.sup.-]([v.sub.1]) {[v.sub.3], [v.sub.5]}. Now, if [v.sub.5] is adjacent to y, then x[v.sub.2][v.sub.3][v.sub.1][v.sub.4][v.sub.5]y is a hamiltonian path of D. Hence [v.sub.5] is not adjacent to y, so [N.sup.-](y) = {[v.sub.2], [v.sub.3]}, which contradicts Corollary 3.4.

Lemmas 3.1 and 3.6 imply the following.

Corollary 3.7 If 2 [less than or equal to] k [less than or equal to] 7, then every k-traceable oriented graph of order n is traceable, where k [less than or equal to] n [less than or equal to] 7.

4 Oriented graphs that are 6-traceable

In this section we prove that the TC holds for k = 6, i.e. that every 6-traceable oriented graph of order at least 11 is traceable. We first prove it for oriented graphs that are not strong.

Lemma 4.1 If D is a 6-traceable oriented graph of order n [greater than or equal to] 11 that is not strong, then D is traceable.

Proof: It follows from Lemma 2.6 that D has a nontrivial strong component X that is nonhamiltonian, and from Lemma 2.5 that |V (X)| = n - 1.

By symmetry we may assume that X = [D.sub.2]. Then [D.sub.1] has only one vertex x. Now [D.sub.2] is 5-traceable and of order n - 1 [greater than or equal to] 10. However, it is shown in (5) that the TC holds for k = 5, so [D.sub.2] is traceable. Let [v.sub.1][v.sub.2]...[v.sub.n - 1], be a hamiltonian path in [D.sub.2].

Let [v.sub.i] be a vertex in [D.sub.2] that is nonadjacent to x. If [d.sup.-]([v.sub.1]) [less than or equal to] n - 6, then D - [N.sup.-]([v.sub.1]) has order at least 6. But if H is any subdigraph of D - [N.sup.-]([v.sub.1]) that has order 6 and contains both [v.sub.1] and x, then H is nontraceable, since neither x nor [v.sub.1] has any in-neighbour in H. This proves that every vertex in D that is not a neighbour of x has in degree at least n - 5. In particular, [d.sup.-]([v.sub.1]) > n - 5. Hence it follows from Lemma 2.2 that [v.sub.3], [v.sub.n-2] [member of] [N.sup.-]([v.sub.1]).

Since X is strong, [v.sub.n - 1] has an out-neighbour [v.sub.i] such that 2 [less than or equal to] i [less than or equal to] n - 3. If [v.sub.n - 1] [member of] [N.sup.+](x), then x[v.sub.n - 1][v.sub.1]...[v.sub.n - 2][v.sub.1]...[v.sub.i - 1] is a hamiltonian path of D. This contradiction shows that [v.sub.n - 1] is not a neighbour of x and hence [d.sup.-] ([v.sub.n - 1]) [greater than or equal to] n - 5.

By Lemma 2.1 [d.sup.+](x) [greater than or equal to] n - 5, so x has at least n - 5 neighbours in the set [v.sub.2]...,,[v.sub.n - 2]. However, if 2 [less than or equal to] i [less than or equal to] n - 2 and [v.sub.i] [member of] [N.sup.i](x), then the predecessor [v.sub.i - 1] is not in [N.sup.-]([v.sub.n - 1]), otherwise D has the hamiltonian path x[v.sub.i]...[v.sub.n - 2][v.sub.1]...[v.sub.i - 1][v.sub.n - 1]. Thus at least n - 5 vertices in [D.sub.2] are not in-neighbours of [v.sub.n - 1], which implies that [d.sup.-]([v.sub.n - 1]) [less than or equal to] 3, contradicting that [d.sup.-]([v.sub.n - 1]) [greater than or equal to] n - 5 [greater than or equal to] 6.

For the proof of the strong case, we also need the following result concerning 6-traceable oriented graphs that are not strong.

Lemma 4.2 If D is a 6-traceable oriented graph of order 8 that is not strong, then D is traceable. Proof: Suppose D is nontraceable. Then, since we have shown that there does not exist a hypotraceable oriented graph of order 7, Lemma 0 implies that D itself is hypotraceable. We need to consider two cases.

Case 1. D has a nontrivial strong component X that is nonhamiltonian: It follows from Lemma that X has order 7. By symmetry we may assume that [D.sub.1] has order 1 and [D.sub.2] = X. Let x be the vertex in [D.sub.1] and let [v.sub.1]...[v.sub.7] be a path in [D.sub.2]. It now follows exactly as in the proof of Lemma 4.1 that [v.sub.3], [v.sub.6] [member of] [N.sup.-]([v.sub.1]) and also that [v.sub.1] and [v.sub.7] are not neighbours of x, and [d.sup.-]([v.sub.1]) [greater than or equal to] 3 and [d.sup.-]([v.sub.7]) [greater than or equal to] 3.

We now consider the possible neighbourhoods of x. By Lemma 2.1 [d.sup.+](x) [greater than or equal to] 3, and by Lemma 2.2 if [d.sup.+](x) = 3, then ([N.sup.+](x)) is nontraceable. Moreover, if [v.sub.1] [member of] [N.sup.+](x), then [v.sub.i - 1] [??] [N.sup.-]([v.sub.7]).

Suppose {[v.sub.2],[v.sub.6]1 [[subset].bar] [N.sup.+](x).Then [N.sup.+]([v.sub.1]) [[subset].bar] {[v.sub.2], [v.sub.4], [v.sub.5]}. But if [v.sub.4] [member of] [N.sup.+]([v.sub.1])then x[v.sub.2][v.sub.3][v.sub.1][v.sub.4][v.sub.5][v.sub.6][v.sub.7] is a hamiltonian path of D. Hence, by Lemma 3.2. [v.sub.5] [member of] [N.sup.+]([v.sub.1]). But then [v.sub.4] [member of] [N.sup.-]([v.sub.1]) and x[v.sub.2][v.sub.3][v.sub.4][v.sub.1][v.sub.5][v.sub.6][v.sub.7] is a hamiltonian path of D. This proves that {[v.sub.2], [v.sub.6]} [??] [N.sup.+](x), so we need to consider four cases.

Case 1.1 {[v.sub.2], [v.sub.3], [v.sub.5] [[subset].bar] [N.sup.+](x): In this case [v.sub.1], [v.sub.2], [v.sub.4] [??] [N.sup.-]([v.sub.7]). Hence [N.sup.-]([v.sub.7]) {[v.sub.3], [v.sub.5], [v.sub.6]}. Since [v.sub.1] [??] [N.sup.+]([v.sub.7]), this implies that [N.sup.+]([v.sub.7]) = {[v.sub.2], [v.sub.4]}. But then x[v.sub.3][v.sub.7][v.sub.4][v.sub.5][v.sub.6][v.sub.1][v.sub.2] is a hamiltonian path of D.

Case 1.2 {[v.sub.2], [v.sub.4], [v.sub.5] [[subset].bar] [N.sup.+](x): In this case [N.sup.-]([v.sub.7]) = {[v.sub.2], [v.sub.5], [v.sub.6]}. But then [N.sup.+]([v.sub.7]) = {[v.sub.3], [v.sub.4]}, which contradicts Lemma since D is hypotraceable.

Case 1.3 {[v.sub.3], [v.sub.4], [v.sub.6] [[subset].bar] [N.sup.+](x): In this case [N.sup.-]([v.sub.7]) {[v.sub.1], [v.sub.4], [v.sub.6]}. If either [v.sub.2] or [v.sub.3] is in [N.sup.+]([v.sub.7]), then D would obviously be traceable. But then [d.sup.+]([v.sub.7]) [less than or equal to] 1, contradicting Lemma 3.2, since D is hypotraceable.

Case 1.4 {[v.sub.3], [v.sub.5], [v.sub.6] [??] [N.sup.+](x): In this case [N.sup.-]([v.sub.7]) = {[v.sub.1], [v.sub.3], [v.sub.6]}. By Lemma 3.4, [d.sup.+]([v.sub.7]) [greater than or equal to] 2. But by Corollary 3.4, [N.sup.+]([v.sub.7]) [not equal to] {[v.sub.4], [v.sub.5]}. Hence [v.sub.2] [member of] [N.sup.+]([v.sub.7]). Now if [v.sub.4] [member of] [N.sup.-]([v.sub.1]), then x[v.sub.5][v.sub.6][v.sub.7][v.sub.2][v.sub.3][v.sub.4][v.sub.1] is a hamiltonian path in D. But we have shown that [d.sup.-]([v.sub.1]) [greater than or equal to] 3, hence [v.sub.5] [member of] [N.sup.-]([v.sub.1]). But then x[v.sub.6][v.sub.7][v.sub.2][v.sub.3][v.sub.4][v.sub.5][v.sub.1] is a hamiltonian path in D.

Case 2 Every strong component of D is hamiltonian. In this case D has at least three strong components, otherwise D would be traceable. By Lemma 3.5 every nontrivial strong component of D has order at least 5. Hence the only possibility is that N([D.sub.1]) = 1, N([D.sub.2]) = 6 and N([D.sub.3]) = 1.

Let x and y be the vertices in [D.sub.1] and [D.sub.3], respectively, and let [v.sub.0][v.sub.1][v.sub.2][v.sub.3][v.sub.4][v.sub.5][v.sub.0] be a hamiltonian cycle of [D.sub.2]. If x has only two neighbours in [D.sub.2], then removal of those two neighbours leaves a nontraceable subdigraph of D that has order 6. Hence x has at least 3 neighbours in [D.sub.2] and, similarly, y has at least three neighbours in [D.sub.2]. But if x is adjacent to [v.sub.1] and j = (i - 1) mod 6, then [v.sub.j] cannot be adjacent to y. This implies that |[N.sup.+](x) [intersection] V([D.sub.2])| = 3 and |[N.sup.-](y) [intersection] V([D.sub.2])| = 3 and [N.sup.+](x) [intersection] [N.sup.-](y) [not equal to] 0. A similar argument to that used in Lemma 2.2 shows that both ([N.sup.+](x) [intersection] V([D.sub.2])) and ([N.sup.-](y) [intersection] V([D.sub.2])) are non traceable.

If [N.sup.+](x) [union] [N.sup.-](y)| [less than or equal to] 3, then D has a subdigraph of order 6 that contains at most one vertex in [N.sup.+](x) [intersection] [N.sup.-](y). But such a subdigraph cannot be traceable. Hence |[N.sup.+](x) [union] [N.sup.-](y)| [greater than or equal to] 4. There are two possibilities to consider: [N.sup.+](x) = {[v.sub.0], [v.sub.1], [v.sub.3]}, [N.sup.-](y) = {[v.sub.1], [v.sub.3], [v.sub.4]} and [N.sup.+](x) = {[v.sub.0], [v.sub.1], [v.sub.4]}, [N.sup.-](y) = {[v.sub.1], [v.sub.2], [v.sub.4]}. In the first case, since D - {[v.sub.0], [v.sub.1]} must be traceable, D must contain the path x[v.sub.3][v.sub.5][v.sub.2][v.sub.4]y. But then D - {[v.sub.3], [v.sub.4]} cannot be traceable. In the second case, D - {[v.sub.1], [v.sub.2]} is nontraceable, since [D.sub.2] - {[v.sub.1], [v.sub.2]} does not have a path starting at [v.sub.0] and ending at [v.sub.4]. Thus either case contradicts the 6-traceability of D.

We are now ready to prove our main theorem.

Theorem 4.3 Every 6-traceable oriented graph of order at least 11 is traceable.

Proof: Suppose, to the contrary that D is a 6-traceable oriented graph of order n that is nontraceable, for some n [greater than or equal to] 11. By Lemma ED we may assume that D is strong. Thus Theorem 2.9 implies that n [less than or equal to] 15. By Theorem 7 D has three independent vertices [x.sub.1], [x.sub.2], [x.sub.3]. Let A = [N.sup.+]([x.sub.1]) and B = V(D) \ (A [union] {[x.sub.1], [x.sub.2], [x.sub.3]}). Lemma 2.8 implies that |A| [less than or equal to] 6 and |B| < 6. Hence, if n = 12, then |A| [greater than or equal to] 3 and |B| [greater than or equal to] 3. If n = 11, then it follows from Lemma 2.2 and the 6-traceability of D that |A| [not equal to] 6 and |B| [not equal to] 6, so in this case 3 [less than or equal to] |A| [less than or equal to] 5 and 3 [less than or equal to] |B| [less than or equal to] 5.

If |B| = 3, then put [S.sub.1] = B [union] {[x.sub.1], [x.sub.2], [x.sub.3]} and [S.sub.2] = {[x.sub.1]} [union] A. If B [greater than or equal to] 4, then put [S.sub.1] = B [union] {[x.sub.1], [x.sub.2]} and [S.sub.2] = {[x.sub.1], [x.sub.3]} [union] A. In either case, 6 [less than or equal to] |[S.sub.1] [less than or equal to] 8 and 6 [less than or equal to] |[S.sub.2]| [less than or equal to] 8, [S.sub.1] [union] [S.sub.2] = V(D) and [S.sub.1] [intersection] [S.sub.2] = {[x.sub.1]}. Moreover, [x.sub.1] has no in-neighbours in [S.sub.2] and no out-neighbours in [S.sub.1], so neither ([S.sub.1]) nor ([S.sub.2]) is strong. Hence, it follows from the 6-traceability of D and Theorem 3.6 and Lemma 4.2 that [S.sub.1] has a hamiltonian path ending in [x.sub.1] and [S.sub.2] has a hamiltonian path starting in [x.sub.1]. But then D has a hamiltonian path, contradicting our assumption.

Corollary 4.4 The OPPC(1) holds for a [less than or equal to] 5.

Corollary 4.5 The OPPC(1) holds for oriented graphs of order at most 12.

Marietjie Frick (1, [dagger]) and Peter Katrenic (2, [double dagger])

(1) University of South Africa, P.O. Box 392, UNISA, 0003 South Africa frickm@unisa.ac.za (2) P.J. Safarik University, Jesennd 5, 04154 Kosice, Slovak Republic peterkatrenic@upjs.sk [dagger] This material is based upon work supported by the National Research Foundation of S.A. under Grant number 2053752 [double dagger] The research of the author is partially supported by Slovak VEGA Grant 1/3004/06 and Slovak VVGS UPJS Grant 11/07-08

received April 2, 2008, revised August]], 2008, accepted October 23, 2008.

Acknowledgements

The collaborative research for this paper was conducted while the first author was on a research visit to the P.J. Safarik University, which was funded by the National Scholarship Programme of the Slovak Republic.

References

[1] J. Bang-Jensen and G. Gutin, Digraphs: Theory, Algorithms and Applications. Springer-Verlag, London, 2002.

[2] J. Bang-Jensen, M. Hegner Nielsen, A. Yeo, Longest path partitions in generalizations of tournaments. Discrete Math. 306 (2006) 1830-1839.

[3] C.C. Chen and P. Manalastas Jr., Every finite strongly connected digraph of stability 2 has a Hamiltonian path. Discrete Math. 44 (1983) 243-250.

[4] M. Frick, S. van Aardt, G. Diamini, J. Dunbar and O. Oellermann, The directed path partition conjecture. Discuss. Math. Graph Theory. 25 (2005) 331-343.

[5] M. Frick, S.A. van Aardt, M.H. Nielsen, O. Oellermann and J.E. Dunbar, A Traceability conjecture for oriented graphs. Submitted.

[6] M. Grotschel, C. Thomassen and Y. Wakabayashi, Hypotraceable digraphs, J. Graph Theory 4 (1980) 377-381.

[7] M. Grotschel and Y Wakabayashi, Constructions of hypotraceable digraphs, Mathematical Programming, Eds. R.W. Cottle, M.L. Kelmanson and B. Korte, Elsevier Science Publishers B.V. (North Holland), 1984.

[8] J.M. Laborde, C. Payan and N.H. Xuong, Independent sets and longest directed paths in digraphs, in: Graphs and other combinatorial topics (Prague, 1982), 173-177 (Teubner-Texte Math. 59, 1983.)

[9] C. Thomassen, Hypohamiltonian graphs and digraphs. In Theory and Applications of graphs, Michigan 1976. Springer Lecture Notes, 642 (1978) 557 - 571.

[10] C.A. Whitehead, M. Frick and S.A. van Aardt, Significant differences between path partitions in directed and undirected graphs. To appear in Utilitas Math.
COPYRIGHT 2008 DMTCS
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2008 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Frick, Marietjie; Katrenic, Peter
Publication:Discrete Mathematics and Theoretical Computer Science
Article Type:Formula
Geographic Code:1USA
Date:Nov 1, 2008
Words:6614
Previous Article:Multidimensional cellular automata and generalization of Fekete's lemma.
Next Article:Simultaneous generation for zeta values by the Markov-WZ method.
Topics:

Terms of use | Privacy policy | Copyright © 2019 Farlex, Inc. | Feedback | For webmasters