Printer Friendly

Traceability of locally hamiltonian and locally traceable graphs.

If P is a given graph property, we say that a graph G is locally P if <N(v)> has property P for every v [member of] V(G) where <N(v)> is the induced graph on the open neighbourhood of the vertex v. Pareek and Skupien (C. M. Pareek and Z. Skupien, On the smallest non-Hamiltonian locally Hamiltonian graph, J. Univ. Kuwait (Sci.), 10:9 - 17, 1983) posed the following two questions.

Question 1 Is 9 the smallest order of a connected nontraceable locally traceable graph?

Question 2 Is 14 the smallest order of a connected nontraceable locally hamiltonian graph?

We answer the second question in the affirmative, but show that the correct number for the first question is 10. We develop a technique to construct connected locally hamiltonian and locally traceable graphs that are not traceable. We use this technique to construct such graphs with various prescribed properties.

Keywords: locally traceable, locally hamiltonian, nonhamiltonian, nontraceable

1 Introduction

Let G be a graph with vertex set V(G) and edge set E(G). The order n(G) and size e(G) of G are the cardinalities of V(G) and E(G), respectively. If X [[subset].bar] V(G) then [X] denotes the subgraph of G induced by X. If v [member of] V(G) then N(v) denotes the open neighbourhood of v in G and N[v] denotes the closed neighbourhood of v in G. A graph G is hamiltonian if it contains a cycle C that contains all the vertices in V(G) and G is traceable if it contains a path P that contains all the vertices in V(G). A graph G is traceable from u to v, where u, v [member of] V(G), if there is a Hamilton path with u and v as end vertices. We define comp(G) to be the number of components of a graph G. Let P = [p.sub.1]...[p.sub.i] and Q = [q.sub.1]... [q.sub.j] be two paths in G. Then the concatenation of the two paths [p.sub.1]... [p.sub.i][q.sub.1]... qj is denoted by PQ. For undefined concepts we refer the reader to [3].

A graph G is called locally hamiltonian if <N(v)> is hamiltonian for every vertex v in G. The notion of local hamiltonicity was introduced by Skupien [11] in 1965. A graph G is called locally connected if <N(v)> is connected for every vertex v in G. The notion of local connectedness was introduced by Chartrand and Pippert [5] in 1974 and has been extensively studied - see for example [11, 6, 4, 7, 10]. A graph G is called locally traceable if <N(v)> is traceable for every vertex v in G. In general, if P is a given graph property, we say that G is locally P if <N(v)> has property P for every v [member of] V(G).

We are particularly interested in the traceability properties of locally connected, locally traceable and locally hamiltonian graphs. We abbreviate locally connected to LC, locally traceable to LT and locally hamiltonian to LH.

Another local property that is often studied in connection with hamiltonicity is the property of being claw-free (i.e. not having [K.sub.1,3] as induced subgraph). Note that a graph G is claw-free if and only if [alpha](<N(v)>) [less than or equal to] 2 for every v [member of] V(G) where [alpha](<N(v)>) is the independence number of <N(v)>. A well-known example where local properties provide valuable information regarding hamiltonicity is the following theorem, proved by Oberly and Sumner [8] in 1979.

Theorem 1.1 [8] If G is a connected LC claw-free graph, then G is hamiltonian.

Note that this implies that a connected LC claw-free graph is also traceable. The requirement that G be claw-free cannot be dropped, even if LC is replaced with LH. In fact, we show that the difference between the number of vertices and the length of a longest path in a connected LH graph may be arbitrarily large.

[FIGURE 1 OMITTED]

In 1983 Pareek and Skupien [10] considered the traceability of LH and LT graphs. Figure 1 depicts a connected nontraceable LH graph of order 14. It was presented in 1972 as an example of a maximal planar nontraceable graph of smallest order by Goodey [7], who also proved that every maximal planar graph of order less than 14 is traceable. It is easily seen that every maximal planar graph is LH. Pareek and Skupien [10] posed the following two questions.

Question 1 Is 9 the smallest order of a connected nontraceable LT graph?

Question 2 Is 14 the smallest order of a connected nontraceable LH graph?

In Section 2 we show that the correct value in Question 1 is 10 and we present the 6 connected nontraceable LT graphs of order 10 that were found by means of a computer search. We also show that the maximum vertex degree of nontraceable LT graphs is at least 6. We develop a technique that we call edge identification to construct nontraceable LT graphs, and use this technique to show that there are planar connected nontraceable LT graphs of all orders greater than 9. We show, moreover, that for every n [greater than or equal to] 10 there exists a connected nontraceable LT graph with maximum degree 7.

In Section 3 we answer the second question in the affirmative by proving that there is no connected nontraceable LH graph of order less than 14. Using a technique called triangle identification we show that there are planar connected nontraceable LH graphs of every order greater than 13. We also show that there exist connected nontraceable LH graphs with minimum vertex degree k for all k [greater than or equal to] 3.

2 Nontraceable LT graphs

We begin this section by defining a construction that will be extensively used in what follows.

Construction 2.1 (Edge identification) Let [G.sub.1] and [G.sub.2] be two LT graphs such that E([G.sub.i]) contains an edge [u.sub.i][v.sub.i] so that there is a Hamilton path in <N([u.sub.i])> that ends at vi and a Hamilton path in <N([v.sub.i])> that ends atui, i = 1,2. Now create a larger graph G by identifying the edges [u.sub.1][v.sub.1] and [u.sub.2][v.sub.2] to a single edge uv (see Figure 2).

[FIGURE 2 OMITTED]

Theorem 2.2 Let [G.sub.1] and [G.sub.2] be two LT graphs that satisfy the conditions of Construction 2.1. If [G.sub.1] and [G.sub.2] are combined by means of edge identification to create a graph G, then G is LT. If G is traceable, then both [G.sub.1] and [G.sub.2] are traceable.

Proof: Let uivi [member of] E([G.sub.i]), i = 1,2 be the two edges used in Construction 2.1 to form the edge uv in E(G).

First suppose w [member of] V(G) - {u, v}. Since the neighbourhood of w is restricted to vertices that are either all in [G.sub.1] or all in [G.sub.2], <[N.sub.G](w)> is traceable.

Now suppose w is one of u and v, say u. Let [Q.sub.1][v.sub.1] be a Hamilton path in <N[G.sub.1] ([u.sub.1])> and let [v.sub.2][Q.sub.2] be a Hamilton path in <N[G.sub.2]([u.sub.2])>, where [Q.sub.1] and [Q.sub.2] are paths in [G.sub.1] and [G.sub.2], respectively. Then [Q.sub.1]v[Q.sub.2] is a Hamilton path in <NG(u)>. Using a similar argument, we can also find a Hamilton path in <NG(v)>. Hence G is LT.

Now assume P is a Hamilton path in G. If uv is an edge of P, then P is of the form illustrated in Figure 3 (a). If uv is not an edge of P, then P is of the form illustrated in Figure 3 (b) or (c). In all three cases it is easy to find Hamilton paths in [G.sub.1] and [G.sub.2]. []

[FIGURE 3 OMITTED]

The following observation will be useful for selecting suitable edges to use in edge identification.

Observation 2.3 Let v be a vertex of degree two in a LT graph. Then any edge incident with v is suitable for use in edge identification.

This can easily be seen by noting that if N(v) = {u, w}, the edge uw is the Hamilton path of <N(v)>, and since [d.sub.<N(v)>] = 1, any Hamilton path of <N(u)> starts at v. In particular, if a LT graph G is combined with [K.sub.3] by means of edge identification to create a graph H, then the vertex v [member of] V([K.sub.3]) that is not incident with the edge used in the procedure, will have degree two. Hence any one of its incident edges will still be suitable for use in edge identification.

The first property of a connected nontraceable LT graph G we will investigate, is a lower bound for [DELTA](G). Theorem 2.4 will be useful in this regard. The graphs [M.sub.3], [M.sub.4] and [M.sub.5] referred to in the theorem are shown in Figure 4.

[FIGURE 4 OMITTED]

A graph G is fully cycle extendable if every vertex in G lies on a 3-cycle and, for every nonhamiltonian cycle C of G, there exists a cycle C' in G that contains all the vertices of C plus a single new vertex.

Theorem 2.4 [1] Suppose G is a connected LT graph with n(G) [greater than or equal to] 3 and [DELTA](G) [less than or equal to] 5. Then G is fully cycle extendable if and only if G [??] {[M.sub.3], [M.sub.4], [M.sub.5]}.

We are now ready to present the following theorem.

Theorem 2.5 If G is a connected nontraceable LT graph, then [DELTA](G) [greater than or equal to] 6, and this bound is sharp.

Proof: Since the graphs [M.sub.3], [M.sub.4] and [M.sub.5] in Figure 4 are traceable, it follows from Theorem 2.4 that [DELTA](G) [greater than or equal to] 6 (a fully cycle extendable graph is hamiltonian, and therefore traceable). Four copies of the graph M3 can be combined using edge identification to create the graph in Figure 5 with maximum degree 6. It is easy to see that this graph is nontraceable. Hence the bound is sharp. []

[FIGURE 5 OMITTED]

Next we answer the first question posed by Pareek and Skupien.

Theorem 2.6 If G is a connected nontraceable LT graph, thenn(G) [greater than or equal to] 10.

Proof: By Theorem 2.5, G has a vertex w of degree k at least 6. Let [v.sub.1][v.sub.2]... [v.sub.k] be a Hamilton path of <N(w)>, and let X = <V(G) - N[w]>.

We make the following observations:

(i) <N[w]> is traceable from [v.sub.i] to [v.sub.i+1] (indices taken modulo k).

(ii) <N[w]> is traceable from [v.sub.1] and [v.sub.k] to any vertex in N[w].

(iii) Since <N[w]> is hamiltonian and G is nontraceable, n(X) [less than or equal to] 2.

(iv) Each component of X has at least two neighbours in N(w).

(v) If comp(X) [greater than or equal to] 2, then X has at least three neighbours in N(w).

Suppose n(G) < 10. Then it follows from Theorem 2.5 and (iii) above that [DELTA](G) = 6, n(X) = 2 and n(G) = 9. Let V(X) = {[x.sub.1],[x.sub.2]}. Since G is nontraceable, [x.sub.1] and [x.sub.2] are nonadjacent. Then by (ii) and (iv), no vertex in X can be adjacent to either [v.sub.1] or [v.sub.6]. If [x.sub.1], say, is adjacent to both [v.sub.i] and [v.sub.i+1] (indices modulo 6), then G - [x.sub.2] is hamiltonian, and therefore G is traceable. If [x.sub.1] is adjacent to vi and [x.sub.2] is adjacent to [v.sub.i+1] (indices modulo 6), then by (i) G is traceable. Hence by (iv) and (v) we have a contradiction. []

A computer search of graphs of order 10 resulted in the 6 nontraceable LT graphs shown in Figure 6. The search was done by constructing all possible graphs of order 10 with maximum vertex degree of either 6 or 7. The graphs were then tested for local traceability and traceability. Finally, graphs that were isomorphic to each other were eliminated from the list of graphs that were found. Since the search space is relatively small, it was feasible to do the search in Visual Basic in MicroSoft Excel. Note that all the graphs in Figure 6 have maximum vertex degree 7. It is reasonably straightforward, although tedious, to prove analytically that every connected nontraceable LT graph of order 10 has maximum vertex degree 7.

[FIGURE 6 OMITTED]

Observation 2.7 If two planar LT graphs [G.sub.1] and [G.sub.2] are combined using edge identification to create graph G, then G is planar.

Theorem 2.8 For any k [greater than or equal to] 10 there exists a connected planar nontraceable LT graph G that has order k and [DELTA](G) = 7.

Proof: Let G0 be the graph LT10A, depicted in Figure 6 and redrawn as the first graph in Figure 7. For each i [greater than or equal to] 1, let Gi be the graph obtained by combining [G.sub.i-1] with a [K.sub.3] by means of edge identification, starting with the edge [v.sub.1][v.sub.2], and after that each time using the edge between the vertices of degree two and three of the last added triangle, as shown in Figure 7. It follows from repeated application of Observation 2.7, that for k > 10, the graph [G.sub.k-10] is a connected planar nontraceable LT graph of order k and it is clear from Figure 7 that it has maximum degree 7. []

Note that the same procedure can be implemented using the graph in Figure 5 to create planar nontraceable LT graphs of any order greater than or equal to 22 with maximum vertex degree 6.

[FIGURE 7 OMITTED]

3 Nontraceable LH graphs

We begin this section by addressing Pareek and Skupien's second question.

As mentioned earlier, the graph in Figure 1 is a connected nontraceable LH graph of order 14. Thus it remains to prove that every LH graph of order less than 14 is traceable.

Pareek [9] claimed that every connected nonhamiltonian LH graph has maximum degree 8. However, as explained in [12], there are gaps in his proof. We were unable to fill those gaps, so we regard Pareek's claim as unproved. However, the following weaker result is valid. It is partly proved in [9] and a complete proof is given in [1].

Theorem 3.1 If G is a connected nonhamiltonian LH graph, then [DELTA](G) [greater than or equal to] 7.

Lemma 3.2 Let G be an LH graph and let v [member of] V(G). Then [alpha](<N(v)>) [less than or equal to] d(v)/2 and G is 3-connected.

Note that if w is any vertex in an LH graph, then <N[w]> contains a wheel as a subgraph. The following two results concerning wheels will be used extensively throughout the proof of our main result in this section.

Lemma 3.3 Let W be a wheel of order d+1, d [greater than or equal to] 3 with centre vertex w and let C be the cycle [v.sub.1]... [v.sub.d][v.sub.1] in N(w). Then W has a Hamilton path between [v.sub.i] and [v.sub.j], for every pair i, j with 1 [less than or equal to] i < j [less than or equal to] d. Moreover every edge of C lies on some Hamilton path between [v.sub.i] and [v.sub.j] except for the edge [v.sub.i][v.sub.j] (when j = i + 1).

[FIGURE 8 OMITTED]

Figure 8 illustrates the Hamilton paths in Observation 3.4 for the cases (b), (c) and (d).

We define a k-path cover of a graph G to be a set of k disjoint paths that contain all the vertices in G.

Observation 3.4 Suppose a graph G contains a wheel W with centre vertex w and let C be the cycle [v.sub.1]... [v.sub.d][v.sub.1] in <N(w)>. Suppose G - V(W) has a k-path cover [Q.sub.1],..., [Q.sub.k]. Let [a.sub.i], [b.sub.i] be the end-vertices of [Q.sub.i], i = 1..., k. (If [Q.sub.i] is a singleton, then [a.sub.i] = [b.sub.i].) Then the following hold.

(a) If k = 1 and [a.sub.1] has a neighbour in C, then G is traceable.

(b) If k = 2 and C contains a pair of distinct vertices {[u.sub.1], [u.sub.2]} such that ui [member of] N([a.sub.i]), i = 1,2, then G is traceable.

(c) Suppose k = 3 and C contains two distinct pairs of distinct vertices {[u.sub.1], [v.sub.1]} and {[u.sub.2], [u.sub.3]} such that [u.sub.i] [member of] N([a.sub.i]) for i = 1,2,3 and [v.sub.1] [member of] N([b.sub.1]). Then G is traceable if the set {[u.sub.1],[v.sub.1], [u.sub.2],[u.sub.3]} contains two consecutive vertices of C.

(d) Suppose k = 4 and C contains three distinct pairs of distinct vertices {[u.sub.1],[v.sub.1]}, {[u.sub.2],[v.sub.2], } and {[u.sub.3], [u.sub.4]} such thatui [member of] N(ai) for i = 1,2,3,4 and [v.sub.i] [member of] N ([b.sub.i]) for i = 1,2. Then G is traceable if either of the following hold.

(i) The vertices [u.sub.2] and [v.sub.2] are the respective successors of [u.sub.1] and [v.sub.1] on C.

(ii) The vertices [u.sub.1] and [v.sub.1] are consecutive vertices of C and the set {[u.sub.2], [v.sub.2], [u.sub.3], [u.sub.4]} contains a pair of consecutive vertices of C.

Note that by "distinct pairs of distinct vertices" we mean that the two vertices in a given pair are distinct and any two given pairs have at most one vertex in common.

Lemma 3.3 implies the following.

Corollary 3.5 If G is a connected nontraceable LH graph, then [DELTA](G) [less than or equal to] n - 4.

Lemma 3.6 Suppose G is a connected LH graph. For any w [member of] V(G), let C = [v.sub.1][v.sub.2]... [v.sub.d][v.sub.1] be a Hamilton cycle in <N(w)> and let X = G - N(w). Let S be the union of any s components of X. Then the following hold.

(i) If for some [v.sub.i] [member of] N(w), [v.sub.i] has at least one neighbour in each component of S, then |[N.sub.C]([v.sub.i]) [intersection] [N.sub.C](V(S))| [greater than or equal to] s + 1 and |[N.sub.C](V(S))| [greater than or equal to] s + 2.

(ii) If s [member of] {2, 3}, then |[N.sub.C](V(S))| [greater than or equal to] s + 2.

Proof:

(i) Since <NS([v.sub.i]) [union] {w}> has at least s + 1 components, and since <N([v.sub.i])> is hamiltonian, <N([v.sub.i]) - {w}> has a Hamilton path P with initial and terminal vertices on C. Since the maximal subpaths of P that intersect each component of S are preceded and followed by vertices on C, |[N.sub.C]([v.sub.i]) [intersection] [N.sub.C](V(S))| [greater than or equal to] s + 1, and since [v.sub.i] [member of] [N.sub.C](V(S)), the result follows.

(ii) Suppose |[N.sub.C](V(S))| [less than or equal to] s + 1. Since G is 3-connected, each component of S has at least 3 neighbours on C, and so, if s [member of] {2,3}, it follows from the pigeonhole principle that there is some vertex [v.sub.i] on C that has a neighbour in each component of S. The result follows from (i). []

The following observation will be used extensively in the proof of our main result in this section.

Observation 3.7 If H is a connected graph of order n [less than or equal to] 5, then one of the following holds.

(a) H is hamiltonian.

(b) H is nonhamiltonian but traceable and H has a Hamilton path Q with end-vertices a, b such that d(a) [less than or equal to] 1, d(b) [less than or equal to] 2 if n [less than or equal to] 4 and d(a) [less than or equal to] 2 if n = 5.

(c) H is nontraceable and has a 2-path cover [Q.sub.1], [Q.sub.2], such that [Q.sub.i] has an end-vertex [a.sub.i] of degree 1 for i = 1,2, and all the end-vertices of [Q.sub.1] and [Q.sub.2] are independent.

(d) H = [K.sub.1, 4].

Figure 9 shows the connected nontraceable graphs of order n [less than or equal to] 5.

[FIGURE 9 OMITTED]

Theorem 3.8 Suppose G is a connected LH graph of order n [less than or equal to] 13. Then G is traceable.

Proof: Suppose to the contrary that G is a connected nontraceable LH graph of n [less than or equal to] 13. Let w be a vertex in G of degree d = [DELTA](G), let C = [v.sub.1]... [v.sub.d][v.sub.1] be a Hamilton cycle in <N(w)> and X = G - N[w]. By Theorem 3.1 and Corollary 3.5, [DELTA](G) [member of] {7, 8, 9}.

Suppose [DELTA](G) = 9. Then |V(X)| [less than or equal to] 3. If E(X) [not equal to] [??], then since G is 3-connected, it follows from Observation 3.4(a) and (b) that D is traceable. If E(X) = [??], it follows from Lemma 3.6(ii), that X has at least two consecutive neighbours on C. Hence, since G is 3-connected, Observation 3.4(c) implies that G is traceable. We may therefore assume [DELTA](G) [member of] {7,8}.

Now let [Q.sub.1],..., [Q.sub.k] be a minimum path cover of X and let [a.sub.i], [b.sub.i] be the end-vertices of [Q.sub.i], i = 1..., k. (If Q has only one vertex, then [a.sub.i] = [b.sub.i].) Since [Q.sub.1],..., [Q.sub.k] is a minimum path cover of X, [a.sub.i][a.sub.j], [b.sub.i][b.sub.j], [a.sub.i][b.sub.j] [??] E(G) for i [not equal to] j.

Claim 1: If [v.sub.i] [member of] C, then [v.sub.i] is adjacent to at most 2 components of X.

Proof of Claim 1: By Lemma 3.2, [v.sub.i] is adjacent to at most [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] components in X, and since [DELTA](G) [member of] {7,8}, we need only consider the case where [DELTA](G) = 8 and some [v.sub.i] [member of] C is adjacent to exactly three components in X. Hence if k = 3 then V(X) = {[a.sub.1], [a.sub.2], [a.sub.3]} or V(X) = {[a.sub.1], [a.sub.2], [a.sub.3], [b.sub.3]}, otherwise k = 4 and V(X) = {[a.sub.1], [a.sub.2],[a.sub.3], [a.sub.4]}. Without loss of generality we may assume {[a.sub.1], [a.sub.2], [a.sub.3]} [subset] N([v.sub.1]). Since [DELTA](G) = 8, it follows from Lemma 3.6(i) that [v.sub.1] has exactly 4 neighbours on C. Since {[a.sub.1], [a.sub.2], [a.sub.3], w} is an independent set in <N([v.sub.1])>, and since <N([v.sub.1])> is Hamiltonian, there exists an [a.sub.i] and aj in N([v.sub.1]), [a.sub.i] [not equal to] [a.sub.j], such that [a.sub.i] [member of] N([v.sub.8]) and [a.sub.j] [member of] N([v.sub.2]). But, since G is 3-connected, this contradicts Observation 3.4(c) if k = 3 and it contradicts Observation 3.4(d)(ii) if k = 4.

We now consider the k-path cover [Q.sub.1],..., [Q.sub.k] of X. There are five cases to consider.

Case k = 1.

Since G is 3-connected, it follows from Observation 3.7(a) and (b) that an end-vertex of [Q.sub.1] has a neighbour on C. Hence by Observation 3.4, G is traceable.

Case k = 2.

Since G is 3-connected, it follows from Observation 3.7(a), (b) and (c) that there are two distinct vertices [u.sub.1] and [u.sub.2] on C such that [u.sub.i] is adjacent to an end-vertex of [Q.sub.i], i = 1,2. Hence, by Observation 3.4, G is traceable.

Case k = 3.

If X is a star [K.sub.1,4], and x its central vertex, then [alpha]<(N(x))> = 4, which contradicts Lemma 3.2, since in this case [DELTA](G) = 7. Hence X has either 2 or 3 components and each component of X has at most 4 vertices and at least one component is a singleton. Thus we may assume that [Q.sub.1] = {[a.sub.1]} and that [a.sub.1] has three distinct neighbours on C. Moreover, by Observation 3.7(a), (b), (c) and the fact that G is 3-connected, we may assume that either each of [a.sub.2] and [a.sub.3] has at least two neighbours on C or [a.sub.2] has at least three neighbours on C and [a.sub.3] has at least one neighbour on C. If a neighbour of [a.sub.3] (or [b.sub.3]) is the successor or predecessor of a neighbour of [a.sub.2] (or [b.sub.2]) on C, it follows from Observation 3.4(c) that G is traceable. Also if two of the neighbours of [a.sub.1] are consecutive on C, Observation 3.4(c) implies that G is traceable.

It remains to consider the case where no neighbour of [a.sub.i] is a successor or predecessor of a neighbour of [a.sub.j] (or [b.sub.j]) on C for i = j, and if [a.sub.i] = [b.sub.i], [a.sub.i] has no consecutive neighbours on C.

If [DELTA](G) = 7 we may therefore assume that N([a.sub.1]) = {[v.sub.1],[v.sub.3],[v.sub.5]} and since <N([a.sub.1])> is hamiltonian, [v.sub.1][v.sub.3], [v.sub.1][v.sub.5],[v.sub.3][v.sub.5] [member of] E(G). Since the set {[a.sub.2], [a.sub.3]} has at least four neighbours in {[v.sub.1], [v.sub.3], [v.sub.5]}, at least one of [v.sub.i], i = 1,3,5, will be of degree 8, a contradiction.

Hence [DELTA](G) = 8 and n(V(X)) [less than or equal to] 4 and V(X) = {[a.sub.1],[a.sub.2],[a.sub.3]} or V(X) = {[a.sub.1],[a.sub.2],[a.sub.3],[b.sub.3]}. But now |[N.sub.C](V(X))| = 4, contradicting Lemma 3.6(ii).

Case k = 4.

If n(X) = 4, V(X) = {[a.sub.1], [a.sub.2],[a.sub.3],[a.sub.4]} and if n(X) = 5, V(X) = {[a.sub.1], [a.sub.2],[a.sub.3],[a.sub.4],[b.sub.4]}. Observe also that since [delta](G) [greater than or equal to] 3, there are at least 12 edges between V(C) and V(X). We make the following claims.

Claim 2: If ak is an isolated vertex in X, and if [v.sub.i] [member of] N(ak), then [v.sub.i-1] [??] N([a.sub.k]) and [v.sub.i+1] [??] N([a.sub.k]). If n(X) = 5 and [v.sub.i] [member of] N([a.sub.4]), then [v.sub.i-1] [??] N ([b.sub.4]) and [v.sub.i+1] [??] N ([b.sub.4]).

Proof of Claim 2: First suppose V(X) = {[a.sub.1], [a.sub.2], [a.sub.3], [a.sub.4]}.

Suppose to the contrary that {[v.sub.1], [v.sub.2]} [[subset].bar] N([a.sub.1]). By Claim 1 and since G is 3-connected, there are at least seven edges between the d - 2 vertices in C - {[v.sub.1], [v.sub.2]} and V(X) - {[a.sub.1]}. By Observation 3.4 (d)(ii), no two consecutive vertices on the path [v.sub.3][v.sub.4] .. .[v.sub.d] have neighbours in V(X) - {[a.sub.1]}. Hence at most [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] vertices on the path [v.sub.3][v.sub.4]... [v.sub.d] are neighbours of X - [a.sub.1]. Since d [member of] {7,8}, no more than three such vertices exist. But then one of these vertices will have at least three neighbours in V(X), contradicting Claim 1.

Now suppose V(X) = {[a.sub.1], [a.sub.2], [a.sub.3], [a.sub.4],[b.sub.4]}. Note that in this case [DELTA](G) = 7.

If [v.sub.1] [member of] N([a.sub.4]) and [v.sub.2] [member of] N([b.sub.4]), the argument above will be directly applicable. So assume without loss of generality that {[v.sub.1],[v.sub.2]} [[subset].bar] N([a.sub.1]). If N([a.sub.2]) [intersection] {[v.sub.1],[v.sub.2]} = [??], then by Observation 3.4(d)(ii), N([a.sub.2]) = {[v.sub.3],[v.sub.5],[v.sub.7]}. Hence, again by Observation 3.4(d)(ii), [N.sub.C]({[a.sub.3],[a.sub.4],[b.sub.4]}) [[subset].bar] {[v.sub.3],[v.sub.5],[v.sub.7]}. But then each of [v.sub.3], [v.sub.5] and [v.sub.7] will have neighbours in three components of X, contrary to Claim 1.

If {[v.sub.1],[v.sub.2]} C N([a.sub.2]), then by Claim 1 and Observation 3.4(d)(ii), N({[a.sub.3],[a.sub.4],[b.sub.4]}) = {[v.sub.4], [v.sub.5], [v.sub.6]}. But since [delta](G) [greater than or equal to] 3, this again contradicts Claim 1. Therefore [a.sub.2], and by symmetry, [a.sub.3], each has exactly one neighbour in {[v.sub.1], [v.sub.2]}. Hence by Observation 3.4(d)(ii) N([a.sub.2], [a.sub.3]) = {[v.sub.1], [v.sub.2], [v.sub.4], [v.sub.6]}. This implies that no vertex in V(C) is adjacent to [a.sub.4] or [b.sub.4] contradicting the fact that G is 3-connected.

Claim 3: [DELTA](G) = 8 and X = {[a.sub.1], [a.sub.2], [a.sub.3],[a.sub.4]}.

Proof of Claim 3: Suppose [DELTA](G) = 7. By Claim 1 and since each component of X has at least three distinct neighbours in V(C), we may assume without loss of generality that [v.sub.1] has neighbours in two components of X. Suppose [v.sub.1] is adjacent to [a.sub.i] and [a.sub.j] where i,j [not equal to] 4. Then by Claim 2, {[a.sub.i], [a.sub.j]} [intersection] N({[v.sub.2],[v.sub.7]}) = [??]. If n(X) = 5 and, say j = 4, then Claim 2 implies that {[a.sub.i], [b.sub.4]} [intersection] N({[v.sub.2], [v.sub.7]}) = [??]. By Lemma 3.6(i), [v.sub.1] has at least three neighbours in V(C) other than [v.sub.2] and [v.sub.7], and since [v.sub.1] is also adjacent to w, d([v.sub.1]) [greater than or equal to] 8, a contradiction.

Claim 4: If [v.sub.i] [member of] N([a.sub.1]) [intersection] N([a.sub.2]), then there exists a [v.sub.j] [not equal to] [v.sub.i] such that [v.sub.j] [member of] N([a.sub.1]) [intersection] N([a.sub.2]).

Proof of Claim 4: Suppose {[a.sub.1], [a.sub.2]} = [N.sub.X]([v.sub.1]). By Claim 2, {[v.sub.2], [v.sub.8]} [intersection] {N([a.sub.1]) [union] N ([a.sub.2])} = [??]. By Lemma 3.6(i) and since [DELTA](G) = 8, [v.sub.1] has exactly three neighbours other than [v.sub.2] and [v.sub.8] in V(C). Since <N([v.sub.1])> is hamiltonian, one of these three neighbours must be adjacent to both [a.sub.1] and [a.sub.2].

Claim 5: d(ai) = 3 for all [a.sub.i] [member of] X.

Proof of Claim 5: Suppose to the contrary that d([a.sub.1]) > 3. Then by Claim 2, d([a.sub.1]) = 4 and we may assume without loss of generality that N([a.sub.1]) = {[v.sub.1], [v.sub.3], [v.sub.5], [v.sub.7]}. By Observation 3.4(d)(i) at most one of {[v.sub.2], [v.sub.4], [v.sub.6], [v.sub.8]} is in N([a.sub.i]), [a.sub.i] = [a.sub.1]. Since [delta](G) [greater than or equal to] 3 this implies that each [a.sub.i] [not equal to] [a.sub.1] is adjacent to at least two vertices in N([a.sub.1]), contradicting Claim 1.

We can now proceed with the main proof of the theorem.

By Claim 5 there are 12 edges between V(C) and V(X). Hence by Claim 1 we may assume without loss of generality that [N.sub.X]([v.sub.1]) = {[a.sub.1], [a.sub.2]}. By Claims 2 and 5 we may also assume that either N([a.sub.1]) = {[v.sub.1],[v.sub.3],[v.sub.5]} or N([a.sub.1]) = {[v.sub.1],[v.sub.3],[v.sub.6]}. By Claim 4, |N([a.sub.1]) [intersection] N([a.sub.2])] [greater than or equal to] 2. Hence, by Claim 1 we may assume that for at least one of [a.sub.3] and [a.sub.4], say [a.sub.4] has no neighbour in N([a.sub.1]). Furthermore, by Observation 3.4(d)(i), no two neighbours of [a.sub.4] are both successors (or both predecessors) of neighbours of [a.sub.1] on C. Also, by Claim 2, no two neighbours of [a.sub.4] are consecutive vertices on C. But then d([a.sub.4]) < 3, a contradiction.

Case k = 5.

In this case X = {[a.sub.1], [a.sub.2], [a.sub.3], [a.sub.4], [a.sub.5]} and [DELTA](G) = 7. Since d([a.sub.i]) [greater than or equal to] 3 there are at least 15 edges between V(C) and V(X). But then some [v.sub.i] on C will be adjacent to at least three components in X contradicting Claim 1. []

The following construction will be used to find nontraceable LH graphs with certain prescribed properties.

Construction 3.9 (Triangle identification) For i = 1,2, let Gi be a LH graph that contains a triangle [X.sub.i] such that for each vertex x [member of] V([X.sub.i]), there is a Hamilton cycle of <N(x)> that contains the edge [X.sub.i] - x. Suppose V([X.sub.i]) = {[u.sub.i], [v.sub.i], [w.sub.i]}, i = 1,2. Now create a larger graph G by identifying the vertices [u.sub.i], i = 1,2 to a single vertex u, and similarly the vertices [v.sub.i], i = 1,2 to v and [w.sub.i], i = 1,2 to w, and by retaining all the edges present in the original two graphs (see Figure 10).

Theorem 3.10 If two LH graphs [G.sub.1] and [G.sub.2] are combined by triangle identification, the resulting graph G is LH. If G is traceable, then both [G.sub.1] and [G.sub.2] are traceable.

Proof: We use the notation defined in Construction 3.9. First we prove that G is LH. Let X be the triangle of G formed by identifying the vertices of X1 and X2 in Construction 3.9. Observe that if y [member of] V([G.sub.1] - [X.sub.1]), then [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], except for a possible label change of vertices in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (y) [intersection] V([X.sub.1]) to the corresponding vertices in V(X). Hence if y [member of] V([G.sub.1] - [X.sub.1]), then <[N.sub.G](y)> is hamiltonian. The same is true for y [member of] V([G.sub.2] - [X.sub.2]). Now suppose y [member of] V(X), say y = u. Let [v.sub.1][Q.sub.1][w.sub.1][v.sub.1] and [w.sub.2][Q.sub.2][v.sub.2][w.sub.2] be Hamilton cycles of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and <N[G.sub.2]([u.sub.2])> respectively. Then v[Q.sub.1]w[Q.sub.2]v is a Hamilton cycle of <NG(u)>. Using a similar argument, we can also find Hamilton cycles for <NG(v)> and <[N.sub.G](w)>.

[FIGURE 10 OMITTED]

Now suppose G is traceable. Since only vertices in V(X) have neighbours in both [G.sub.1] and [G.sub.2], Figure 11 shows the possible patterns that a Hamilton path in G can follow. The Hamilton path in Figure 11(a) uses two edges of X, the ones in Figure 11(b)-(d) use only one edge of X and the ones in Figure 11(e)-(i) do not use any edge of X. In each case it is easily seen that each of [G.sub.1] and [G.sub.2] has a Hamilton path. []

We are now in a position to use triangle identification to obtain nontraceable LH graphs with specific properties.

Theorem 3.11 If two planar LH graphs [G.sub.1] and [G.sub.2] are combined using triangle identification, the resulting graph G is planar.

Proof: First we show that a separating triangle (a separating triangle is a triangle that does not border a face in a plane representation of the graph) is not suitable for use in triangle identification. Let [v.sub.1],[v.sub.2] and [v.sub.3] be the vertices of a separating triangle in [G.sub.1]. Since LH graphs are 3-connected, each vertex in the separating triangle has neighbours both inside the triangle and outside the triangle. It follows that in <N([v.sub.1])> the edge [v.sub.2][v.sub.3] is a cut edge and is therefore not part of a Hamilton cycle in <N([v.sub.1])>. Therefore the triangle is not suitable for triangle identification.

Let [X.sub.1] and [X.sub.2] be the respective triangles of [G.sub.1] and [G.sub.2] that were used in the triangle identification procedure of Construction 3.9 to form the triangle X of G. Since [G.sub.1] and [G.sub.2] are planar, [G.sub.1] can be drawn such that the edges of [X.sub.1] border the outer face of [G.sub.1], and [G.sub.2] can be drawn such that the edges of X2 border an inner face of [G.sub.2] in a plane representation. The triangle identification procedure will then essentially draw [G.sub.1] - [X.sub.1] inside X and [G.sub.2] - [X.sub.2] outside X. Hence the resulting graph G is planar. []

Observation 3.12 There exists a planar LH graph G of order n for every n [greater than or equal to] 4 such that [DELTA](G) [less than or equal to] 6.

Proof: Such a graph can be constructed in the following manner: start with [K.sub.4] drawn in a plane representation. Attach an additional vertex to the three outer vertices in [K.sub.4] to create graph [G.sub.5]. Keep repeating this procedure (add an additional vertex by connecting it to the three outer vertices in [G.sub.i]). The procedure essentially starts off with [K.sub.4], which is LH, and in each step uses triangle identification to combine [G.sub.i] with [K.sub.4], so it is clear that the new graph [G.sub.i+1] is also LH. Moreover, by drawing the graph in each step so that edges between the last three vertices added border the outer plane, the maximum vertex degree can be limited to six. See Figure 12. []

[FIGURE 11 OMITTED]

Theorem 3.13 There exists a connected planar nontraceable LH graph of order n with [DELTA](G) [less than or equal to] 10 for every n [greater than or equal to] 14.

Proof: First note that the nontraceable LH graph of order 14 in Figure 13 is planar. This is the same graph as shown in Figure 1 redrawn in a more convenient representation. Also note the three vertices of the LH graphs constructed in Observation 3.12 that border the outer plane are suitable for use in triangle identification. Label these three vertices u, v and w having degrees 3,4 and 5, respectively. By identifying u with [v.sub.5] in Figure 13, v with [v.sub.2], and w with [u.sub.5], we get a planar nontraceable LH graph G with maximum vertex degree of 10. If we start with an LH graph H from Observation 3.12 of order k, k [greater than or equal to] 4, then n(G) = 11 + k. []

[FIGURE 12 OMITTED]

[FIGURE 13 OMITTED]

Theorem 3.14 For any integer k [greater than or equal to] 3 there exists a nontraceable LH graph G with [delta](G) = k.

Proof: To construct such a graph we start with the order 14 nontraceable LH graph H shown in Figure 13. Since complete graphs of order greater than 3 are LH, we can construct the graph G by combining multiple copies of [K.sub.k+1] with G by means of triangle identification in such a way that each vertex of H is used at least once in a triangle identification procedure. Since a triangle can be used only once in triangle identification, we must use a new triangle for each step.

To see that a triangle with vertices [x.sub.1], [x.sub.2] and [x.sub.3] in a LH graph [G.sub.1] can only be used once in triangle identification to combine [G.sub.1] with a LH graph [G.sub.2], note that before triangle identification the edge [x.sub.2][x.sub.3] is part of a Hamilton cycle in (N[G.sub.1] ([x.sub.1])}. After triangle identification, the edge [x.sub.2][x.sub.3] is replaced in the Hamilton cycle in <[N.sub.G]([x.sub.1])> by a path with vertices that originated from [G.sub.2]. The same constraint does not apply to vertices.

Specifically, the triangles formed by edges between the vertices in the following sets in V(H) can be used: {[v.sub.1],[u.sub.1],[v.sub.2]}, {[v.sub.1],[u.sub.2],[v.sub.3]}, {[v.sub.1],[u.sub.3],[v.sub.4]}, {[v.sub.1],[u.sub.4],[v.sub.5]}, {[v.sub.2],[v.sub.3],[u.sub.6]}, {[v.sub.3],[v.sub.4],[u.sub.7]}, {[v.sub.5],[v.sub.6],[u.sub.8]}, and {[v.sub.5], [v.sub.2], [u.sub.5] }. This results in the graph in Figure 14 (in this case [K.sub.5] was used for the triangle identification, so the minimum vertex degree is 4). []

[FIGURE 14 OMITTED]

Finally we show that the difference between the order n of a LH graph G and the length of a longest path in G can be made arbitrarily large.

Theorem 3.15 For any natural number k > 0 there exists a LH graph G such that the difference between the order n of G and the length of a longest path in G is at least k.

Proof: Consider the nontraceable LH graph [G.sub.0] in Figure 13 and let [U.sub.0] = {[u.sub.1],... , [u.sub.8]} represent the vertices of degree 3 in [G.sub.0]. Note that [U.sub.0] is an independent set of cardinality 8. Hence, since |V([G.sub.0]) -[U.sub.0]| =6, any path in [G.sub.0] omits at least one vertex in [U.sub.0]. Let [G.sub.i], i = 1,..., m be m copies of [G.sub.0], and denote the vertex in V([G.sub.i]) corresponding to [u.sub.j] in [U.sub.0] by [u.sub.i,j] and the vertex in V([G.sub.i]) corresponding to vj in V([G.sub.0]) - [U.sub.0] by [v.sub.i,j]. We construct the graph [DELTA][G.sub.k] by combining the graph [DELTA][G.sub.k-1], with [G.sub.k] using triangle identification in the following way. For k = 2, combine [G.sub.1] with [G.sub.2] by means of Construction 3.9 by identifying the vertices [v.sub.1,2], [v.sub.1,3] and [u.sub.1,6] with [v.sub.2,5], [v.sub.2,4] and [u.sub.2,8], respectively, and retaining the labels [v.sub.1,2], [v.sub.1],3, [u.sub.1,6] for the new vertices to form [DELTA][G.sub.2]. In general, combine [DELTA][G.sub.k-1] with [G.sub.k] by indentifying [v.sub.k-1,2], [v.sub.k-1,3] and [u.sub.k-1,6] with [v.sub.k,5], [v.sub.k,4] and [u.sub.k,8], respectively, and retaining the labels [v.sub.k-1,2], [v.sub.k-1,3], and [u.sub.k-16] to form [DELTA][G.sub.k], for k = 3,..., m. Now let G = [DELTA][G.sub.m]. Then n(G) = 11m+3. Let U be the set of all vertices in G labeled [u.sub.q,p], where q and p are any subscripts found in V(G). Then U| = 7m +1 and V(G) - U, with | V(G) - U|= 4m + 2, contains all the vertices labeled [v.sub.q,p]. Since [U.sub.0] is an independent set, it follows from our triangle identification procedure, that U is also an independent set of vertices. Hence a longest path in G omits at least (7m + 1) - (4m + 2) - 1 = 3m - 2 vertices in U. Now let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],i.e. G is constructed by means of repeated triangle identification of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] copies of [G.sub.0]. Then the difference between the n(G) and the length of a longest path in G is at least k. []

Note that in the construction used in the proof of Theorem 3.15, the maximum vertex degree of G is 14 regardless of the difference between the order of G and the length of a longest path in G.

4 Conclusion

Some questions that are still unanswered are the following:

* What is the smallest size of a connected nontraceable LT graph with n vertices? The smallest size that we found is 2n - 1, but connected LT graphs of size 2n - 3 exist. However, Astratian and Oksimets [2] showed that LT graphs that are not maximal outerplanar (maximal outerplanar graphs are hamiltonian) have size at least 2n - 2.

* We found connected nontraceable LT graphs with maximum vertex degree of 6 for all orders greater than or equal to 22, but we do not know what the smallest order for such a graph is.

* What is the minimum value of [DELTA](G) if G is a connected nontraceable LH graph? We know the number is at least 7, but the we do not know of any nontraceable LH graph with [DELTA](G) < 8.

* We have shown that there exist connected nontraceable LH graphs with maximum vertex degree no greater than 10 for all orders greater than 13. This bound is probably not sharp. We think it likely that best possible limit is 9.

Acknowledgements

The authors wish to thank the University of South Africa and the National Research Foundation of South Africa for their sponsorship of the Salt Rock Workshop of 28 July - 10 August 2013 which contributed towards results in this paper.

The authors would also like to thank Marietjie Frick for many valuable discussions and comments.

References

[1] S.A. van Aardt, M. Frick, O. Oellermann and J. P. de Wet, Global cycle properties in locally connected, locally traceable and locally hamiltonian graphs, Discrete Appl. Math., 205:171 - 179, 2016.

[2] A.S. Asratian and N. Oksimets, Graphs with hamiltonian balls, Australasian J. Comb. 17: 185 -198, 1998.

[3] A. Bondy and U.S.R Murty, Graph theory, Springer, 2008.

[4] D. Barnette and E. Jucovic, Hamiltonian circuits on 3-polytopes, J. Combinatorial Theory, 9:54-59, 1970.

[5] G. Chartrand and R. Pippert, Locally connected graphs, Cas. pest, mat., 99:158 - 163, 1974.

[6] G. Ewald, On shortness exponents of families of graphs, Israel J. of Mathematics, 16:53-61, 1973.

[7] P. R. Goodey, Hamiltonian paths on 3-polytopes, J. Combinatorial Theory Series B, 12:143-152, 1972.

[8] D. Oberly and P. Sumner, Every locally connected nontrivial graph with no induced claw is hamiltonian, Journal of Graph Theory, 3:351-356, 1979.

[9] C. M. Pareek, On the maximum degree of locally hamiltonian non-hamiltonian graphs, Utilitas Mathematica, 23:103-120, 1983.

[10] C. M. Pareek and Z. Skupien, On the smallest non-hamiltonian locally hamiltonian graph, J. Univ. Kuwait (Sci.), 10:9 - 17, 1983.

[11] Z. Skupien, Locally hamiltonian graphs and Kuratowski's theorem, Bull. Acad. Polon. Sci., Ser. Sci. Math. Astronom. Phys., 13:615-619, 1965.

[12] J. P. de Wet, M. Frick and S. A. van Aardt, Hamiltonicity of locally traceable and locally hamiltonian graphs, submitted.

Johan P. de Wet Susan A. van Aardt (*)

University of South Africa, UNISA, South Africa

received 3rd May 2015, revised 10th June 2016, accepted 16th June 2016.

(*) This material is based upon work supported by the National Research Foundation of S.A. under Grant number 81075
COPYRIGHT 2016 DMTCS
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2016 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:de Wet, Johan P.; van Aardt, Susan A.
Publication:DMTCS Proceedings
Article Type:Report
Date:Jan 1, 2016
Words:8561
Previous Article:On the complexity of edge-colored subgraph partitioning problems in network optimization.
Next Article:Edge disjoint Hamilton cycles in Knodel graphs.
Topics:

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