Ayesha Shabbir^a , Carol T. Zamfirescu^b , Tudor I. Zamfirescub,c,a

^a"Abdus Salam" School of Mathematical Sciences, GC University,

68-B, New Muslim Town, Lahore, Pakistan

^bFaculty of Mathematics, University of Dortmund,

Dortmund, Germany

^c"Simion Stoilow" Institute of Mathematics, Roumanian Academy,

Bucharest, Roumania

ashinori@hotmail.com, czamfirescu@gmail.com, tuzamfirescu@gmail.com

This is a survey of results obtained during the last 45 years regarding the intersection behaviour of all longest paths, or all longest cycles, in connected graphs. Planar graphs and graphs of higher connectivity receive special attention. Graphs embeddable in the cubic lattice of arbitrary dimension, and graphs embeddable in the triangular or hexagonal lattice of the plane are also discussed. Results concerning the case when not all, but just some longest paths or cycles are intersected, for example two or three of them, are also reported.

Keywords: longest path, longest cycle, planar graph, lattice, torus, Mobius strip, Klein bottle ¨ Mathematics Subject Classification : 05-02, 05C38, 05C35

1. Empty intersection of all longest paths

In a connected graph (undirected and without loops or multiple edges), two longest paths meet. This is easily seen. Do all longest paths meet? This problem was raised by Gallai [12] in 1966, when hypotraceable graphs had not yet been uncovered.

This paper is a survey about Gallai's problem and variants of it involving conditions on connectivity, planarity or embeddability on other surfaces, and also considering cycles instead of paths.

Received: 10 January 2013, Accepted: 6 February 2013.

Reducing the number of longest paths or cycles to be intersected, leads to other challenging problems, also surveyed here. For a previous, shorter survey, see [51].

We call P1 the question: "Do there exist graphs, in which any vertex is missed by some longest path?" Walther was the first who found such a graph in 1969 [42]. A few years later, an example with 12 vertices only was (independently) found by Walther and the third author, see [43, 14, 50] and Fig. 1(a).

The P1 problem restricted to planar graphs, generated several examples, each smaller than the previous one. Walther's first example with 25 vertices was planar, but the smallest so far was found by Schmitz [31] in 1975 and has 17 vertices, see Fig. 1(b).

It was conjectured [48] that the orders 12 and 17 are smallest possible for the problem P1 in the arbitrary and planar case, respectively. Brinkmann and Van Cleemput [5] proved (using computers) that in the arbitrary case the order 12 is minimal.

Figure 1.

The examples become naturally larger if higher connectivity is requested. The first 2-connected example constructed in 1972 for P1 had 82 vertices and was planar [47]. Currently, the smallest known 2-connected graph answering P1 has 26 vertices and was found by Skupień [37] in 1996, while the smallest known planar example has order 32 and was found by the third author [50] in 1976, see Fig. 2.

Figure 2.

The same problem for 3-connected graphs received its first answer in 1974 through Grünbaum's example with 484 vertices [14]. But the best answer so far, again provided by the third author [50], is a graph with 36 vertices obtained by opening up Petersen's graph at some vertex and introducing it at all vertices of \(K_4\).

Concerning the problem P1 for 3-connected planar graphs, with the help of his hypohamiltonian planar graph, Hatzel [15] obtained in the same way a 3-connected planar graph satisfying P1, of order 224. Exhibiting smaller planar hypohamiltonian graphs, the second and the third author [46] decreased the order to 188; then Araya and Wiener [44] lowered it to 164, and finally (so far!) Jooyandeh, McKay, Östergård, Pettersson, and the second author [20] decreased it to 156.

Impulses coming from fault-tolerant designs in computer networks (for fault-tolerance problems in Graph Theory see, for example, [16, 45, 18, 8, 28, 29]) led to considering P1 in lattices. Let \(\mathcal{T}\), \(\mathcal{L}\) and \(\mathcal{H}\) be the usual triangular, square and hexagonal lattice in the plane, respectively. Notice that \(\mathcal{H} \subset \mathcal{L} \subset \mathcal{T}\). The connectivity of any finite connected graph in \(\mathcal{T}\) is at most 3, while in \(\mathcal{L}\) or \(\mathcal{H}\) it is at most 2. Unfortunately, the previously mentioned graphs are not embeddable in \(\mathcal{T}\). We prove this here for Schmitz' graph S of Fig. 1(b). Indeed, the vertices 12 and 13 of S must be interior to one of the two regions bounded by the cycles (6,7,8,9,10,11,6) and (5,6,11,10,9,14,5). But no hexagon in \(\mathcal{T}\) has more than one interior vertex.

Dino and the third author [11] established the existence of a graph in \(\mathcal{T}\) with 30 vertices verifying P1, see Fig. 3(a). In 2012, Nadeem, the first and the third author [27] found a subgraph of \(\mathcal{L}\) of order 46 answering P1, see Fig. 3(b). As an example in \(\mathcal{H}\), the three authors presented in the same paper a graph of order 94, see Fig. 3(c). These three graphs (of order 30, 46, and 94, respectively) are in fact homeomorphic.

Figure 3.

[11] and [27] provide, for P1 in \(\mathcal{T}\) and \(\mathcal{L}\), 2-connected graphs homeomorphic to the graph Z (see Fig. 2(b)), of order 92 (a non-bipartite graph) and 126, respectively, see Figs. 4(a) and (b). A graph of order 244, embedded in \(\mathcal{H}\), appears in [27], see Fig. 4(c). This graph is not homeomorphic to Z (which has vertices of degree 4).

No 3-connected graph satisfying P1 seems to exist in \(\mathcal{T}\).

The torus also admits lattices of the above three kinds.

Consider an \((m+1) \times (n+1)\) parallelogram (with (m+1)(n+1) vertices) in \(\mathcal{T}\). By identifying opposite vertices on the boundary as indicated on Fig. 5(a), we obtain the toroidal triangular lattice \(\mathcal{T}_{m,n}^T\). It has mn vertices. The toroidal square lattice \(\mathcal{L}_{m,n}^T\) and the toroidal hexagonal lattice \(\mathcal{H}_{m,n}^T\) are defined similarly, see Figs. 5(b) and (c), respectively.

In [35], the first and the third author succeeded to embed the graph W of Fig. 1(a) in \(\mathcal{T}_{4,3}^T\) as a spanning graph, see Fig. 6(a). In [33], the same authors proved the existence of examples in \(\mathcal{L}_{5,4}^T\) and \(\mathcal{H}_{12,6}^T\) by embedding two homeomorphic graphs of order 20 and 58, respectively, as shown in Figs. 6(b) and (c). The first graph is a spanning subgraph of \(\mathcal{L}_{5,4}^T\). It first appeared in [48].

Figure 6.

The first and the third author [35] provided an answer to P1 for 2-connected graphs in triangular toroidal lattices by exhibiting a graph of order 48 homeomorphic to Z in \(\mathcal{T}_{7,8}^T\), see Fig. 7(a). In the case of square toroidal lattices, the same authors [33] embedded another homeomorphic copy of Z, of order 80, in \(\mathcal{L}_{10,10}^T\), see Fig. 7(b).

Just like on the torus, lattices of these three kinds are well defined on the Möbius strip and Klein bottle, too.

A triangular lattice on the Möbius strip \(\mathcal{T}_{m,n}^M\) is defined according to Figs. 8(a) and (b), with respective orders mn and \(\frac{n}{2}(2m+1)\). The square lattice on the Möbius strip \(\mathcal{L}_{m,n}^M\) with mn vertices is defined as indicated in Fig. 8(c), and the hexagonal lattice on the Möbius strip \(\mathcal{H}_{m,n}^M\) of order mn is defined according to Figs. 8(d) and (e).

Figure 8.

The first and the third author [35, 33] proved that Schmitz' graph S with 17 vertices is embeddable in T M 4,4 and L M 3,8 , respectively, see Figs. 9(a) and (b). But it is not realizable in H^M m,n for any values of m and n, because in S the cycles (3, 8, 7, 6, 5, 4, 3) and (9, 8, 7, 6, 11, 10, 9) of length 6 meet at three vertices, while in H any two intersecting hexagons meet exactly at two vertices. [33] shows a graph homeomorphic to S, with 46 vertices, answering P1 and embeddable in H^M 7,9 , see Fig. 9(c).

The same authors provide in [35] a 2-connected graph homeomorphic to Z, of order 64, answering P1 and embeddable in T M ⁸,¹¹ (shown in Fig. 10(a)). In [33], they show such a graph of order 112 embedded in L M ¹⁰,14, see Fig. 10(b).

Figure 9.

Figure 10.

A triangular lattice on the Klein bottle \(\mathcal{T}_{m,n}^K\) of order mn is defined according to Fig. 11(a). And, according to Figs. 11(b) and (c), we define the square lattice on the Klein bottle \(\mathcal{L}_{m,n}^K\) and the hexagonal lattice on the Klein bottle \(\mathcal{H}_{m,n}^K\) of order mn.

Figure 11.

The first author [32] succeeded to embed the graphs W and S of Figs. 1(a) and (b) in \(\mathcal{T}_{4,3}^K\) (see Fig. 12(a)) and \(\mathcal{L}_{6,4}^K\) (see Fig. 12(b)), respectively. In the same paper, a graph of order 58 verifying P1 and embeddable in \(\mathcal{H}_{12,6}^K\) is presented (see Fig. 12(c)).

Figure 12.

In [32] the first author showed how the 2-connected examples answering P1, of order 48 and 80, and embeddable in \(\mathcal{T}_{7,8}^T\) and \(\mathcal{L}_{10,10}^T\), can also be embedded in \(\mathcal{T}_{7,8}^K\) and \(\mathcal{L}_{10,10}^K\), respectively. See Figs. 13(a) and (b).

The last result about P1, which we are recording here, is an embedding of S in the 3-dimensional cubic lattice \(\mathcal{L}^3\) found by Bashir and the third author, see [4] and Fig. 14.

Figure 13.

Figure 14.

2. Empty intersection of all longest cycles

The Ck problem, i.e. the existence of graphs in which any k vertices are missed by some longest cycle, was completely solved, in the sense that the provided example has the smallest possible number of vertices (namely 3k + 3), by Thomassen [39]. See Fig. 15.

Figure 15.

However, it can be said that the appropriate frame while working with longest cycles demands connectivity at least 2, and in that case the smallest known example for the C1 problem remains, as for connectivity 3, Petersen's graph. That this graph is smallest possible among all 2-connected graphs, was verified by Brinkmann and Van Cleemput [5].

For the C1 problem and 2-connected planar graphs, Thomassen found an example with 15 vertices (see [50] and Fig. 16).

Figure 16.

Again, Brinkmann and Van Cleemput proved its optimality [5]. For 3-connected planar graphs, the first example was found by Grunbaum [14] in 1974 and had ¨ 124 vertices. Two years later, Thomassen [40] found the first planar hypohamiltonian graph of 105 vertices. In 1979, Hatzel [15] found such graph on 57 vertices only. In 2007, the second and the third author [46] decreased this to 48, and in 2010, Araya and Wiener [44] further improved it to 42. The hypohamiltonian planar graph with 40 vertices recently found by Jooyandeh, McKay, Osterg ¨ ard, Pettersson, and the second ˚ author [20], is the smallest example known to date.

The graph of Fig. 15 is clearly embeddable in T and obvious modifications of it, of order 4k+4 and 6k + 6, can be embedded in L and H, respectively. See [34].

For 2-connected graphs, the first answer to C1 in any lattice is due to Wegner, who found a graph in L of order 95 (see [25, p. 202]). Nadeem, the first and the third author [27] found a subgraph of H satisfying C1, of order 170. An example with 60 vertices in T is presented by the first and the third author in [35]. Later on, these three results were improved by Dino, the second and the third author [10], their examples being homeomorphic to Thomassen's graph T of Fig. 16, and having order 33 in T , 35 in L and 89 in H. See Fig. 17.

Figure 17.

The first and the third author [33] discovered that the graph T spans \(\mathcal{L}_{5,3}^T\) (see Fig. 18(a)), and consequently also \(\mathcal{T}_{5,3}^T\). Moreover, they embedded a homeomorphic copy of T of order 30 verifying C1 in \(\mathcal{H}_{10,4}^T\), see Fig. 18(b).

Figure 18.

The 2-connected graph Y of Fig. 19(a), of order 12, found by the third author (see [19]), also answers C1. The first and the third author [33] embedded Y in \(\mathcal{L}_{4,3}^M\) as a spanning graph, see Fig. 19(b). This result is best possible. Indeed, Brinkmann and Van Cleemput [5] verified using computers that the only graph on less than 12 vertices verifying C1 is the Petersen graph, which is not embeddable in \(\mathcal{L}_{m,n}^M\) for any m,n. Indeed, the Petersen graph has two disjoint 5-cycles, but no \(\mathcal{L}_{m,n}^M\) contains two disjoint 5-cycles. Clearly, Y spans \(\mathcal{T}_{4,3}^M\), too. In [33], the first and the third author presented a graph homeomorphic to Y of order 32 verifying C1, which spans \(\mathcal{H}_{8,4}^M\), see Fig. 19(c).

The first author [32] embedded Y in \(\mathcal{T}_{6,2}^K\), \(\mathcal{L}_{6,2}^K\) and \(\mathcal{H}_{6,2}^K\), as a spanning graph, see Figs. 20(a), (b) and (c), respectively. The latter two are smallest possible (see the argument above).

The first graph embeddable in \(\mathcal{L}^3\) and verifying C1 was found by Bashir and the third author [4]. It has order 40. A smaller such graph (of order 17) is shown in Fig. 21, and was found by Dino, the second and the third author [10]. This graph has also smaller order than a graph with 20 vertices embeddable in \(\mathcal{L}^4\), previously found by Bashir and the third author [4].

Figure 19.

Figure 20.

Figure 21.

3. Avoiding arbitrary pairs of points

The C2 problem, received – for 2-connected graphs – a positive answer as well. The first 2-connected example was presented already in 1970 by Walther [42] and had 220 vertices.

The chronologically first 3-connected example was found in 1974 by Grünbaum [14]. The upto-date smallest such example known was presented in 1976 and has 75 vertices. It is obtained by opening up the Petersen graph P at a vertex, inserting it in place of every vertex of a copy P' of P, and eventually contracting all original edges of P'.

Concerning planar 2-connected graphs, an example constructed by the third author [48] in 1975 is still the smallest known. It has 135 vertices. If the graph should be 3-connected, the first example, with 14818 vertices, was found by the third author [50] in 1976.

By providing and using smaller and smaller planar hypohamiltonian graphs, the results improved. In 1979, Hatzel [15] found an example with 6758 vertices. In 2007, the second and the

third author [46] improved this bound by showing the existence of a graph of order 4277. Three years later, Araya and Wiener [44] found one with 3701 vertices. Recently, Jooyandeh, McKay, Osterg ¨ ard, Pettersson, and the second author got the smallest to date, with ˚ 3525 vertices.

Schauerte and the second author have shown that there also exist cubic 3-connected planar graphs satisfying C2 [30]. They provided an example of order 8742. Araya and Wiener [1] found an example of order 4830 only.

In [35], the first and the third author provided a graph of order 375 answering C2 and embeddable in T (see Fig. 22), while in [34], they established the existence of such graphs in L and H, of order 490 and 950, respectively. See Figs. 23 and 24.

Figure 22.

Figure 23.

Figure 24.

In the same paper, the authors embedded a graph verifying C2 with 235 vertices in \(\mathcal{T}_{25,11}^T\), see Fig. 25. [34] shows graphs of order 315 and 600, which are embedded in \(\mathcal{L}_{26,16}^T\) and \(\mathcal{H}_{30,32}^T\), respectively. See Figs. 26 and 27.

Figure 25.

In [34, 35], the first and the third author also established the existence of graphs answering C2 in all these three types of lattices on the Möbius strip. See [35] and Fig. 28 for an example of C2 of order 235 embedded in \(\mathcal{T}^{M}_{12,33}\). See [34] and Figs. 29 and 30, where two graphs verifying C2 of order 350 and 670 are embedded in \(\mathcal{L}^{M}_{34,18}\) and \(\mathcal{H}^{M}_{42,28}\), respectively.

[32] shows that 2-connected examples answering C2, can be found in \(\mathcal{T}_{25,11}^T\), \(\mathcal{L}_{26,16}^T\) and \(\mathcal{H}_{30,32}^T\), with respective order 235, 315 and 600, and are also embeddable in \(\mathcal{T}_{11,25}^K\), \(\mathcal{L}_{26,18}^K\) and \(\mathcal{H}_{30,32}^K\), respectively. See Figs. 31, 32 and 33.

Bashir [3] presents a 2-connected graph answering C2, of order 210, in \(\mathcal{L}^3\), see Fig 34.

The problem P2 of finding graphs in which every pair of vertices is missed by some longest path, was solved by Grünbaum in 1974, see [14]. His graph was 3-connected and had 324 vertices.

Figure 26.

Figure 27.

Now the smallest such examples are a graph with 93 vertices and a 3-connected graph with 270 vertices, found by the third author [50] in 1976. Concerning planar graphs, a graph of order 308 and a 2-connected graph of order 914, found in 1975 by the third author [49] are still the smallest known. For 3-connected graphs, the first example with 57838 was given by the third author [50] in 1976. Hatzel [15] in 1979 improved this bound to 26378. The second and the third author [46] in 2007, and Araya and Wiener [44] in 2010, further consecutively reduced this bound to 16926,

Figure 28.

Figure 29.

respectively 14694. Currently, the best known bound is 10350, proven by Jooyandeh, McKay, Osterg ¨ ard, Pettersson, and the second author [20]. ˚

In the family of lattices, we can report only one result of the above type, obtained by Bashir [3]. He found a graph verifying P2 with 207 vertices, embedded in L 3 ; see Fig. 35.

Figure 30.

Figure 31.

Figure 32.

Figure 33.

Figure 34.

4. Non-empty intersection of all longest paths or cycles

There are several families of graphs in which all longest paths (or cycles) must have a common point. An important such family is that of all trees. In every tree, each longest path contains its centre. In 1990, Klavžar and Petkovšek [21] proved that split graphs and cacti negatively answer P1 as well. Very recently, de Rezende, Fernandes, Martin and Wakabayashi [9] strengthened a result of Axenovich and showed that outerplanar graphs also never answer positively P1. They also extended this property, shared – as we mentioned above – by all trees, to the class of all 2-trees. Menke [25] proved in 2000 that in any grid graph all longest cycles must have at least four common points (see also [26]).

Figure 35.

5. Intersecting three longest paths

What happens if we do not intersect all longest paths, but just some of them? The intersection does not decrease. If they are few enough, will the intersection become non-empty? Yes, if you take just two of them, it is easily seen to be non-empty. What, if you take three? This is unknown, and intriguing. Anyway, there must exist a minimal number p such that, in any connected graph, any family of p longest paths has non-empty intersection. Find p. This short question was asked by the third author in the eighties, see Voss' book [41, p. 78].

What is known about p? In Schmitz' graph of Fig. 1(b), there are 7 longest paths whose intersection is void. So,

\[2 \le p \le 6\].

Regarding the analogous number c defined in 2-connected graphs only, in the same way as p, but with "cycles" instead of "paths", a small graph we already met in a previous section, see Fig. 19(a), has 8 longest cycles with no common point. However, Jendrol' and Skupień [19] have shown that

\[2 \le c \le 6\]

holds, by exhibiting a graph having only 7 longest cycles with empty intersection, see Fig. 36.

Perhaps any 6 longest paths (or cycles) always meet. But this should be even more difficult to prove than the variant with 3 instead of 6.

Since no proof is in sight yet, several results have been obtained about special classes of graphs. So, in 2009 Axenovich [2] showed that in outerplanar graphs any 3 longest paths meet, but - as mentioned in the previous section - in fact all of them meet. Later de Rezende, Fernandes, Martin, and Wakabayashi [9], starting from Axenovich's result, proved that in every (connected) graph with hamiltonian non-trivial blocks, any 3 longest paths meet.

Figure 36.

6. Intersecting two longest paths or two longest cycles

Consider two longest paths in a connected graph. It is easy to show that they must meet. Also quite easy to see is that in any 2-connected graph any two longest paths or cycles have at least two points in common. In fact the following old conjecture from 1984, attributed to Scott Smith, is known: In a k-connected graph, k ≥ 2, any two longest cycles meet in at least k vertices.

Grotschel [13] proved Smith's conjecture for ¨ k ≤ 6. In the general case, Burr and the third author [6] showed that in a ^k-connected graph, ^{k ≥ 2}, every two longest cycles meet in at least ^√ k vertices. A proof of this result can be found in [17]. Chen, Faudree, and Gould [7] asymptotically improved this as follows. Consider a k-connected graph, k ≥ 2. Then every two longest cycles meet in at least ck³/⁵ vertices, where c ≈ 0.2615.

Concerning longest paths, we have an analogous conjecture stated by Hippchen [17]: In a kconnected graph, k ≥ 2, any two longest paths meet in at least k vertices. Kk,2k+2 shows that the conjecture is tight. It was proven by Hippchen [17] for k = 3.

We recall that W ⊂ V (G) is an articulation set, if deleting W renders G disconnected. Grotschel [13] proved that, if ¨ k ≤ 5 and G is a graph of order at least k + 1, in which two longest cycles meet in a set W of cardinality k, then W is an articulation set.

Grotschel [13] showed that the " ¨ 5" in above theorem is best possible. Grotschel [13] went ¨ on to conjecture that if one adds the condition that G has circumference at least k + 1, then this restricted version of his theorem holds for k ∈ {6, 7}. (The Petersen graph shows that this "7" is best possible.) Stewart [38] proved this conjecture; he showed that if k ∈ {6, 7}, and G is a graph of circumference at least k + 1, and furthermore C and C 0 are distinct longest cycles in G meeting in a set W of cardinality k, then W is an articulation set of G.

Sheppardson [36] studied the following version of the Smith conjecture: If C and D are largest bonds (i.e. minimal, non-empty sets of edges whose removal disconnects the graph) in a k-connected graph G, then the number of components in G−(C ∪ D) is at least k + 2−|C ∩ D|. Both this conjecture and Smith's original conjecture have been proven only for small k. Sheppardson proves a linear lower bound on the number of components of G − (C ∪ D) which holds for all values of k ≥ 7. For more background on this, see [24, 22, 23].

Acknowledgement

The third author's work was partly supported by a grant of the Roumanian National Authority for Scientific Research, CNCS UEFISCDI, project number PN-II-ID-PCE-2011-3-0533.

References

• [1] M. Araya and G. Wiener, On cubic planar hypohamiltonian and hypotraceable graphs, Electron. J. Combin. 18 (2011), #P85.
• [2] M. Axenovich, When do three longest paths have a common vertex?, Discrete Math. Algorithms Appl. 1 (2009), 115–120.
• [3] Y. Bashir, Highly non-concurrent longest paths and cycles in lattices, in preparation.
• [4] Y. Bashir and T. Zamfirescu, Lattice graphs with Gallai's property, to appear in Bull. Math. Soc. Sci. Math. Roumanie 56 (2013), 65–71.
• [5] G. Brinkmann and N. Van Cleemput, private communication.
• [6] S. A. Burr and T. Zamfirescu, unpublished manuscript.
• [7] G. Chen, R. Faudree, and R. Gould, Intersections of Longest Cycles in k-Connected Graphs, J. Combin. Theory, Ser. B 72 (1998), 143–149.
• [8] Y.-C. Chen, C.-H. Tsai, L.-H. Hsu, and J. J. M. Tan, On some super fault-tolerant Hamiltonian graphs, Appl. Math. Comput. 148 (2004), 729–741.
• [9] S. F. de Rezende, C. G. Fernandes, D. M. Martin, and Y. Wakabayashi, Intersection of longest paths in a graph, submitted.
• [10] A. Dino, C. T. Zamfirescu, and T. I. Zamfirescu, Lattice graphs with non-concurrent longest cycles, submitted.
• [11] A. Dino and T. Zamfirescu, On longest paths in triangular lattice graphs, Util. Math. 89 (2012), 269–273.
• [12] T. Gallai, Problem 4, in: Theory of Graphs, Proc. Tihany 1966 (eds.: P. Erdos & G. Katona), ¨ Academic Press, New York, 1968, p. 362.
• [13] M. Grotschel, On intersections of longest cycles, in: "Graphy Theory and Combinatorics" ¨ (ed.: B. Bollobas), pp. 171–189, Academic Press, London, 1984. ´
• [14] B. Grunbaum, Vertices missed by longest paths or circuits, ¨ J. Combin. Theory, Ser. A 17 (1974), 31–38.
• [15] W. Hatzel, Ein planarer hypohamiltonian Graph mit 57 Knoten, Math. Ann. 243 (1979), 237– 246.
• [16] J. P. Hayes, A Graph Model for Fault-Tolerant Computing Systems, IEEE Transactions on Computers 25 (1976), 875–884.
• [17] T. Hippchen, Master Thesis, Georgia State Univ. (2008).

• [18] C.-N. Hung, L.-H. Hsu, and T.-Y. Sung, On the Construction of Combined k-Fault-Tolerant Hamiltonian Graphs, Networks 37 (2001), 165–170.
• [19] S. Jendrol' and Z. Skupien, Exact number of longest cycles with empty intersection, ´ Europ. J. Combin. 18 (1997), 575–578.
• [20] M. Jooyandeh, B. D. McKay, P. R. J. Osterg ¨ ard, V. H. Pettersson, and C. T. Zamfirescu, ˚ Planar hypohamiltonian graphs on 40 vertices, submitted.
• [21] S. Klavzar and M. Petkov ˇ sek, Graphs with nonempty intersection of longest paths, ˇ Ars Combin. 29 (1990), 13–52.
• [22] M. Lemos, T. J. Reid, B. Williams, and H. Wu, Pairs of largest circuits in 3-connected matroids, Lin. Alg. Appl. 427 (2007), 313–316.
• [23] N. McMurraya, T. J. Reid, L. Sheppardson, B. Wei, and H. Wu, On deletions of largest bonds in graphs, Discrete Math. 308 (2008), 1137–1141.
• [24] N. McMurraya, T. J. Reid, B. Wei, and H. Wu, Largest circuits in matroids, Adv. Appl. Math. 34 (2005), 213–216.
• [25] B. Menke, Longest cycles in grid graphs, Studia Sci. Math. Hung. 36 (2000), 201–230.
• [26] B. Menke, Ch. Zamfirescu, and T. Zamfirescu, Intersections of longest cycles in grid graphs, J. Graph Theory 25 (1997), 37–52.
• [27] F. Nadeem, A. Shabbir, and T. Zamfirescu, Planar lattice graphs with Gallai's property, Graphs Combin., DOI: 10.1007/s00373-012-1177-8.
• [28] J.-H. Park, H.-C. Kim, and H.-S. Lim, Fault-hamiltonicity of hypercube-like interconnection networks, Proc. of IEEE International Parallel and Distributed Processing Symposium IPDPS 2005, Denver, Apr. 2005.
• [29] J.-H. Park, H.-S. Lim, and H.-C. Kim, Panconnectivity and pancyclicity of hypercube-like interconnection networks with faulty elements, Theoret. Comput. Sci. 377 (2007), 170–180.
• [30] B. Schauerte and C. T. Zamfirescu, Regular graphs in which every pair of points is missed by some longest cycle, An. Univ. Craiova, Ser. Mat. Inf. 33 (2006), 154–173.
• [31] W. Schmitz, Uber l ¨ angste Wege und Kreise in Graphen, ¨ Rend. Sem. Mat. Univ. Padova 53 (1975), 97–103.
• [32] A. Shabbir, Fault-tolerant designs in lattice networks on the Klein bottle, submitted.
• [33] A. Shabbir and T. Zamfirescu, Gallai's property for graphs in lattices on the torus and Mobius ¨ strip, submitted.

• [34] A. Shabbir and T. Zamfirescu, Highly non-concurrent longest cycles in lattice graphs, Discrete Math., DOI: 10.1016/j.disc.2012.03.015.
• [35] A. Shabbir and T. Zamfirescu, Fault-tolerant designs in triangular lattice networks, submitted.
• [36] L. Sheppardson, Intersections of largest bonds in k-connected graphs, Discrete Math. 309 (2009), 4116–4122.
• [37] Z. Skupien, Smallest sets of longest paths with empty intersection, ´ Combin. Probab. Comput. 5 (1996), 429–436.
• [38] I. A. Stewart, Univ. Newcastle upon Tyne, Computing Laboratory, Technical Report Series, no. 241 (1987).
• [39] C. Thomassen, Hypohamiltonian graphs and digraphs, in: Theor. Appl. Graphs, Proc. Kalamazoo 1976, Lect. Notes Math. 642 (1978), 557–571.
• [40] C. Thomassen, Planar and infinite hypohamiltonian and hypotraceable graphs, Discrete Math. 14 (1976), 377–389.
• [41] H.-J. Voss, Cycles and Bridges in Graphs, VEB Deutscher Verlag der Wissenschaften, Berlin, 1991.
• [42] H. Walther, Uber die Nichtexistenz eines Knotenpunktes, durch den alle l ¨ angsten Wege eines ¨ Graphen gehen, J. Combin. Theory 6 (1969), 1–6.
• [43] H. Walther and H.-J. Voss, Uber Kreise in Graphen ¨ , VEB Deutscher Verlag der Wissenschaften, Berlin, 1974.
• [44] G. Wiener and M. Araya, On planar hypohamiltonian graphs, J. Graph Theory 67 (2011), 55–68.
• [45] T. Yamada and S. Ueno, Fault-tolerant graphs for tori, Networks 32 (1998), 181–188.
• [46] C. T. Zamfirescu and T. I. Zamfirescu, A hypohamiltonian planar graph with 48 vertices, J. Graph Theory 55 (2007), 338–342.
• [47] T. Zamfirescu, A two-connected planar graph without concurrent longest paths, J. Combin. Theory, Ser. B 13 (1972), 116–121.
• [48] T. Zamfirescu, L'histoire et l'etat pr ´ esent des bornes connues pour ´ P j k , C j k , P j k et C j k , Cahier du CERO 17 (1975), 427–439.
• [49] T. Zamfirescu, Graphen, in welchen je zwei Eckpunkte von einem langsten Weg vermieden ¨ werden, Ann. Univ. Ferrare 21 (1975), 17–24.
• [50] T. Zamfirescu, On longest paths and circuits in graphs, Math. Scand. 38 (1976), 211–239.
• [51] T. Zamfirescu, Intersecting longest paths or cycles: A short survey, Analele Univ. Craiova, Seria Mat. Inf. 28 (2001), 1–9.