Intersecting longest paths and longest cycles: A survey
---
paper_title: Panconnectivity and pancyclicity of hypercube-like interconnection networks with faulty elements

paper_content:

In this paper, we deal with the graph G"[email protected]?G"1 obtained from merging two graphs G"0 and G"1 with n vertices each by n pairwise nonadjacent edges joining vertices in G"0 and vertices in G"1. The main problems studied are how fault-panconnectivity and fault-pancyclicity of G"0 and G"1 are translated into fault-panconnectivity and fault-pancyclicity of G"[email protected]?G"1, respectively. Many interconnection networks such as hypercube-like interconnection networks can be represented in the form of G"[email protected]?G"1 connecting two lower dimensional networks G"0 and G"1. Applying our results to a class of hypercube-like interconnection networks called restricted HL-graphs, we show that in a restricted HL-graph G of degree m(>=3), each pair of vertices are joined by a path in [email protected]?F of every length from 2m-3 to |V([email protected]?F)|-1 for any set F of faulty elements (vertices and/or edges) with |F|@?m-3, and there exists a cycle of every length from 4 to |V([email protected]?F)| for any fault set F with |F|@?m-2.
---
paper_title: Gallai’s property for graphs in lattices on the torus and the Möbius strip

paper_content:

We prove the existence of graphs with empty intersection of their longest paths or cycles as subgraphs of lattices on the torus and the Mobius strip.
---
paper_title: Planar Lattice Graphs with Gallai's Property

paper_content:

In 1966 T. Gallai asked whether connected graphs with empty intersection of their longest paths do or do not exist. After examples of such graphs were found, the question was extended to graphs of higher connectivity, and to cycles instead of paths. Examples being again found, for connectivity up to 3, the question has been asked whether there exist large families of graphs without Gallai's property. The family of grid graphs, a special kind of graphs embedded in the planar square lattice $${\mathcal {L}}$$ , has been shown by B. Menke to contain no graph enjoying Gallai's property. In this paper we find several examples of graphs embedded in $${\mathcal {L}}$$ and enjoying that property with respect to both paths and cycles.
---
paper_title: On some super fault-tolerant Hamiltonian graphs

paper_content:

A k-regular Hamiltonian and Hamiltonian connected graph G is super fault-tolerant Hamiltonian if G remains Hamiltonian after removing at most k-2 nodes and/or edges and remains Hamiltonian connected after removing at most k-3 nodes and/or edges. A super fault-tolerant Hamiltonian graph has a certain optimal flavor with respect to the fault-tolerant Hamiltonicity and Hamiltonian connectivity. In this paper, we investigate a construction scheme to construct super fault-tolerant Hamiltonian graphs. In particularly, twisted-cubes, crossed-cubes, and Mobius cubes are all special cases of this construction scheme. Therefore, they are all super fault-tolerant Hamiltonian graphs.
---
paper_title: Lattice graphs with non-concurrent longest cycles

paper_content:

No hypohamiltonian graphs are embeddable in the planar square lattice. This lattice contains, however, graphs in which every vertex is missed by some longest cycle. In this paper we present graphs with this property, embeddable in various lattices, and of remarkably small order.
---
paper_title: Highly nonconcurrent longest paths and cycles in lattices

paper_content:

We investigate here the connected graphs with the property that any pair of vertices are missed by some longest paths (or cycles), embeddable in n-dimensional lattices Ln where L denotes the set of integers.
---
paper_title: On Longest Paths in Triangular Lattice Graphs

paper_content:

In this note we present two graphs embeddable into the equilateral triangular lattice and satisfying Gallai's property that every vertex is missed by some longest path.
---
paper_title: A Graph Model for Fault-Tolerant Computing Systems

paper_content:

An approach to fault-tolerant design is described in which a computing system S and an algorithm A to be executed by S are both defined by graphs whose nodes represent computing facilities. A is executable by S if A is isomorphic to a subgraph of S.A k-fault is the removal of k nodes (facilities) from S.S is a k-fault tolerant (k-FT) realization of A if A can be executed by S with any k-fault present in S. The problem of designing optimal k-FT systems is considered where A is equated to a 0-FT system. Techniques are described for designing optimal k-FT realizations of single-loop systems; these techniques are related to results in Hamiltonian graph theory. The design of optimal k-FT realizations of certain types of tree systems is also examined. The advantages and disadvantages of the graph model are discussed.
---
paper_title: Fault-tolerant graphs for tori

paper_content:

Motivated by the design of fault-tolerant multiprocessor interconnection networks, this paper considers the following problem: Given a positive integer t and a graph H, construct a graph C from H by adding a minimum number /spl Delta/(t,H) of edges such that even after deleting any t edges from G the remaining graph contains H as a subgraph. We estimate /spl Delta/(t,H) for the torus, which is well-known as a very important interconnection network for multiprocessor systems.
---
paper_title: Intersections of Longest Cycles in k-Connected Graphs

paper_content:

LetGbe a connected graph, wherek?2. S. Smith conjectured that every two longest cycles ofGhave at leastkvertices in common. In this note, we show that every two longest cycles meet in at leastck3/5vertices, wherec?0.2615.
---
paper_title: On planar hypohamiltonian graphs

paper_content:

We present a planar hypohamiltonian graph on 42 vertices and (as a corollary) a planar hypotraceable graph on 162 vertices, improving the bounds of Zamfirescu and Zamfirescu and show some other consequences. We also settle the open problem whether there exists a positive integer N, such that for every integer n≥N there exists a planar hypohamiltonian/hypotraceable graph on n vertices. © 2010 Wiley Periodicals, Inc. J Graph Theory 67: 55-68, 2011 © 2011 Wiley Periodicals, Inc.
---
paper_title: On the Constructon of Combined k-fault tolerant Hamiltonian Graphs

paper_content:

A graph G G is a combined kk-fault-tolerant Hamiltonian graph (also called a combined kk-Hamiltonian graph) if G F is Hamiltonian for every subset F (V V(G) [ [ E(G G)) with |F F |= kk. A combined kk-Hamiltonian graph G with |V V(G)| = n is optimal if it has the minimum number of edges among all nn-node k-Hamiltonian graphs. Using the concept of node expansion, we present a powerful construction scheme to construct a larger combined k-Hamiltonian graph from a given smaller graph. Many previous graphs can be constructed by the concept of node expansion. We also show that our construction maintains the optimality property in most cases. The classes of optimal combined k-Hamiltonian graphs that we constructed are shown to have a very good diameter. In particular, those optimal combined 1Hamiltonian graphs that we constructed have a much smaller diameter than that of those constructed previously by Mukhopadhyaya and Sinha, Harary and Hayes,
---
paper_title: Lattice Graphs With Gallai’s Property

paper_content:

We investigate graphs with the property that all longest paths or all longest cycles have empty intersection. In this paper, we nd such graphs as subgraphs of cubic lattices.
---
paper_title: Vertices missed by longest paths or circuits

paper_content:

Abstract : Let G denote a graph with v(G) vertices, and let c(G) and p(G) denote the maximal numbers of vertices contained in any simple circuit or path in G. The author denotes by c(j,k) (p(j,k)) the greatest lower bounds of v(G) where G is a k-connected graph such that for every choice of j vertices of G there exists in G a simple circuit (path) with c(G) (p(G)) vertices that misses the j chosen vertices. Analogously defined numbers with G restricted to planar graphs are denoted by (c sub 0)(j,k) and (p sub 0)(j,k). Extending various known results it is established that (c sub 0)(1,3) < or = 124, (p sub 0)(1,3) < or = 484, c(2.3) < or = 90 and p(2.3) < or = 324. (Modified author abstract)
---
paper_title: Planar Hypohamiltonian Graphs on 40 Vertices

paper_content:

A graph is hypohamiltonian if it is not Hamiltonian, but the deletion of any single vertex gives a Hamiltonian graph. Until now, the smallest known planar hypohamiltonian graph had 42 vertices, a result due to Araya and Wiener. That result is here improved upon by 25 planar hypohamiltonian graphs of order 40, which are found through computer-aided generation of certain families of planar graphs with girth 4 and a fixed number of 4-faces. It is further shown that planar hypohamiltonian graphs exist for all orders greater than or equal to 42. If Hamiltonian cycles are replaced by Hamiltonian paths throughout the definition of hypohamiltonian graphs, we get the definition of hypotraceable graphs. It is shown that there is a planar hypotraceable graph of order 154 and of all orders greater than or equal to 156. We also show that the smallest hypohamiltonian planar graph of girth 5 has 45 vertices.
---
paper_title: Fault-Hamiltonicity of hypercube-like interconnection networks

paper_content:

We call a graph G to be f-fault Hamiltonian (resp. f-fault Hamiltonian-connected,) if there exists a Hamiltonian cycle (resp. if each pair of vertices are joined by a Hamiltonian path) in G /spl bsol/ F for any set F of faulty elements with |F| /spl les/ f. In this paper, we deal with the graph G/sub 0/ /spl oplus/ G/sub 1/ obtained from connecting two graphs G/sub 0/ and G/sub 1/ with n vertices each by n pairwise nonadjacent edges joining vertices in G/sub 0/ and vertices in G/sub 1/. Provided each G/sub i/ is f-fault Hamiltonian-connected and f+1-fault Hamiltonian, 0 /spl les/ i /spl les/ 3, we show that G/sub 0/ /spl oplus/ G/sub 1/ is f+1-fault Hamiltonian-connected for any f /spl ges/ 2 and f+2-fault Hamiltonian for any f /spl ges/ 1, and that for any f /spl ges/ 0, H/sub 0/ /spl oplus/ H/sub 1/ is f+2-fault Hamiltonian-connected and f+3-fault Hamiltonian, where H/sub 0/ = G/sub 0/ /spl oplus/ G/sub 1/ and H/sub 1/ = G/sub 2/ /spl oplus/ G/sub 3/. Many interconnection networks such as hypercube-like interconnection networks can be represented in the form of G/sub 0/ /spl oplus/ G/sub 1/ connecting two lower dimensional networks G/sub 0/ and G/sub 1/. Applying our main results to a subclass of hypercube-like interconnection networks, called restricted HL-graphs, which include twisted-cubes, crossed cubes, multiply twisted cubes, Mobius cubes, Mcubes, and generalized twisted cubes, we show that every restricted HL-graph of degree m( /spl ges/ 3) is m - 3-fault Hamiltonian-connected and m - 2-fault Hamiltonian.
---
paper_title: Intersection of Longest Paths in a Graph

paper_content:

Abstract In 1966, Gallai asked whether every connected graph has a vertex that is common to all its longest paths. The answer to this question is negative. We prove that the answer is positive for outerplanar graphs. Another related question was raised in 1995 at the British Combinatorial Conference: Do any three longest paths in a connected graph have a vertex in common? We prove that, in a connected graph in which all non-trivial blocks are Hamiltonian, any three of its longest paths have a common vertex. Both of these results strengthen a recent result by Axenovich.
---
paper_title: Highly nonconcurrent longest paths and cycles in lattices

paper_content:

We investigate here the connected graphs with the property that any pair of vertices are missed by some longest paths (or cycles), embeddable in n-dimensional lattices Ln where L denotes the set of integers.
---
paper_title: Highly non-concurrent longest cycles in lattice graphs

paper_content:

Abstract There exist planar graphs in which any two vertices are missed by some longest cycle. Although this requirement is very strong, we prove here that such graphs can also be found as subgraphs of the square and hexagonal lattices. Considering (finite) such lattices on the torus and on the Mobius strip enables us to reduce the order of our examples.
---
paper_title: On planar hypohamiltonian graphs

paper_content:

We present a planar hypohamiltonian graph on 42 vertices and (as a corollary) a planar hypotraceable graph on 162 vertices, improving the bounds of Zamfirescu and Zamfirescu and show some other consequences. We also settle the open problem whether there exists a positive integer N, such that for every integer n≥N there exists a planar hypohamiltonian/hypotraceable graph on n vertices. © 2010 Wiley Periodicals, Inc. J Graph Theory 67: 55-68, 2011 © 2011 Wiley Periodicals, Inc.
---
paper_title: Lattice Graphs With Gallai’s Property

paper_content:

We investigate graphs with the property that all longest paths or all longest cycles have empty intersection. In this paper, we nd such graphs as subgraphs of cubic lattices.
---
paper_title: Vertices missed by longest paths or circuits

paper_content:

Abstract : Let G denote a graph with v(G) vertices, and let c(G) and p(G) denote the maximal numbers of vertices contained in any simple circuit or path in G. The author denotes by c(j,k) (p(j,k)) the greatest lower bounds of v(G) where G is a k-connected graph such that for every choice of j vertices of G there exists in G a simple circuit (path) with c(G) (p(G)) vertices that misses the j chosen vertices. Analogously defined numbers with G restricted to planar graphs are denoted by (c sub 0)(j,k) and (p sub 0)(j,k). Extending various known results it is established that (c sub 0)(1,3) < or = 124, (p sub 0)(1,3) < or = 484, c(2.3) < or = 90 and p(2.3) < or = 324. (Modified author abstract)
---
paper_title: Planar Hypohamiltonian Graphs on 40 Vertices

paper_content:

A graph is hypohamiltonian if it is not Hamiltonian, but the deletion of any single vertex gives a Hamiltonian graph. Until now, the smallest known planar hypohamiltonian graph had 42 vertices, a result due to Araya and Wiener. That result is here improved upon by 25 planar hypohamiltonian graphs of order 40, which are found through computer-aided generation of certain families of planar graphs with girth 4 and a fixed number of 4-faces. It is further shown that planar hypohamiltonian graphs exist for all orders greater than or equal to 42. If Hamiltonian cycles are replaced by Hamiltonian paths throughout the definition of hypohamiltonian graphs, we get the definition of hypotraceable graphs. It is shown that there is a planar hypotraceable graph of order 154 and of all orders greater than or equal to 156. We also show that the smallest hypohamiltonian planar graph of girth 5 has 45 vertices.
---
paper_title: Regular graphs in which every pair of points is missed by some longest cycle

paper_content:

In Petersen’s well-known cubic graph every vertex is missed by some longest cycle. Thomassen produced a planar graph with this property. Grunbaum found a cubic graph, in which any two vertices are missed by some longest cycle. In this paper we present a cubic planar graph fulfilling this condition. 2000 Mathematics Subject Classification. 05C38.
---
paper_title: Fault-tolerant designs in lattice networks on the Klein bottle

paper_content:

In this note, we consider triangular, square and hexagonal lattices on the flat Klein bottle, and find subgraphs with the property that for any $j$ vertices there exists a longest path (cycle) avoiding all of them. This completes work previously done in other lattices.
---
paper_title: Gallai’s property for graphs in lattices on the torus and the Möbius strip

paper_content:

We prove the existence of graphs with empty intersection of their longest paths or cycles as subgraphs of lattices on the torus and the Mobius strip.
---
paper_title: Planar Lattice Graphs with Gallai's Property

paper_content:

In 1966 T. Gallai asked whether connected graphs with empty intersection of their longest paths do or do not exist. After examples of such graphs were found, the question was extended to graphs of higher connectivity, and to cycles instead of paths. Examples being again found, for connectivity up to 3, the question has been asked whether there exist large families of graphs without Gallai's property. The family of grid graphs, a special kind of graphs embedded in the planar square lattice $${\mathcal {L}}$$ , has been shown by B. Menke to contain no graph enjoying Gallai's property. In this paper we find several examples of graphs embedded in $${\mathcal {L}}$$ and enjoying that property with respect to both paths and cycles.
---
paper_title: Lattice graphs with non-concurrent longest cycles

paper_content:

No hypohamiltonian graphs are embeddable in the planar square lattice. This lattice contains, however, graphs in which every vertex is missed by some longest cycle. In this paper we present graphs with this property, embeddable in various lattices, and of remarkably small order.
---
paper_title: Highly non-concurrent longest cycles in lattice graphs

paper_content:

Abstract There exist planar graphs in which any two vertices are missed by some longest cycle. Although this requirement is very strong, we prove here that such graphs can also be found as subgraphs of the square and hexagonal lattices. Considering (finite) such lattices on the torus and on the Mobius strip enables us to reduce the order of our examples.
---
paper_title: On planar hypohamiltonian graphs

paper_content:

We present a planar hypohamiltonian graph on 42 vertices and (as a corollary) a planar hypotraceable graph on 162 vertices, improving the bounds of Zamfirescu and Zamfirescu and show some other consequences. We also settle the open problem whether there exists a positive integer N, such that for every integer n≥N there exists a planar hypohamiltonian/hypotraceable graph on n vertices. © 2010 Wiley Periodicals, Inc. J Graph Theory 67: 55-68, 2011 © 2011 Wiley Periodicals, Inc.
---
paper_title: Lattice Graphs With Gallai’s Property

paper_content:

We investigate graphs with the property that all longest paths or all longest cycles have empty intersection. In this paper, we nd such graphs as subgraphs of cubic lattices.
---
paper_title: Vertices missed by longest paths or circuits

paper_content:

Abstract : Let G denote a graph with v(G) vertices, and let c(G) and p(G) denote the maximal numbers of vertices contained in any simple circuit or path in G. The author denotes by c(j,k) (p(j,k)) the greatest lower bounds of v(G) where G is a k-connected graph such that for every choice of j vertices of G there exists in G a simple circuit (path) with c(G) (p(G)) vertices that misses the j chosen vertices. Analogously defined numbers with G restricted to planar graphs are denoted by (c sub 0)(j,k) and (p sub 0)(j,k). Extending various known results it is established that (c sub 0)(1,3) < or = 124, (p sub 0)(1,3) < or = 484, c(2.3) < or = 90 and p(2.3) < or = 324. (Modified author abstract)
---
paper_title: Planar Hypohamiltonian Graphs on 40 Vertices

paper_content:

A graph is hypohamiltonian if it is not Hamiltonian, but the deletion of any single vertex gives a Hamiltonian graph. Until now, the smallest known planar hypohamiltonian graph had 42 vertices, a result due to Araya and Wiener. That result is here improved upon by 25 planar hypohamiltonian graphs of order 40, which are found through computer-aided generation of certain families of planar graphs with girth 4 and a fixed number of 4-faces. It is further shown that planar hypohamiltonian graphs exist for all orders greater than or equal to 42. If Hamiltonian cycles are replaced by Hamiltonian paths throughout the definition of hypohamiltonian graphs, we get the definition of hypotraceable graphs. It is shown that there is a planar hypotraceable graph of order 154 and of all orders greater than or equal to 156. We also show that the smallest hypohamiltonian planar graph of girth 5 has 45 vertices.
---
paper_title: Exact Numbers of Longest Cycles with Empty Intersection

paper_content:

We have proved that, for every integer??7,there is a 2-connected graph having?longest cycles the intersection of which is empty, but any set of?-1longest cycles has a non-empty intersection. This implies a new bound,c?6,on a parametercintroduced by T. Zamfirescu.
---
paper_title: Vertices missed by longest paths or circuits

paper_content:

Abstract : Let G denote a graph with v(G) vertices, and let c(G) and p(G) denote the maximal numbers of vertices contained in any simple circuit or path in G. The author denotes by c(j,k) (p(j,k)) the greatest lower bounds of v(G) where G is a k-connected graph such that for every choice of j vertices of G there exists in G a simple circuit (path) with c(G) (p(G)) vertices that misses the j chosen vertices. Analogously defined numbers with G restricted to planar graphs are denoted by (c sub 0)(j,k) and (p sub 0)(j,k). Extending various known results it is established that (c sub 0)(1,3) < or = 124, (p sub 0)(1,3) < or = 484, c(2.3) < or = 90 and p(2.3) < or = 324. (Modified author abstract)
---
paper_title: Intersections of longest cycles in grid graphs

paper_content:

It is well-known that the largest cycles of a graph may have empty inter- section. This is the case, for example, for any hypohamiltonian graph. In the literature, several important classes of graphs have been shown to contain examples with the above property. This paper investigates a (nontrivial) class of graphs which, on the contrary, admits no such example. c 1997 John Wiley & Sons, Inc. J Graph Theory 25: 37{52, 1997
---
paper_title: Intersection of Longest Paths in a Graph

paper_content:

Abstract In 1966, Gallai asked whether every connected graph has a vertex that is common to all its longest paths. The answer to this question is negative. We prove that the answer is positive for outerplanar graphs. Another related question was raised in 1995 at the British Combinatorial Conference: Do any three longest paths in a connected graph have a vertex in common? We prove that, in a connected graph in which all non-trivial blocks are Hamiltonian, any three of its longest paths have a common vertex. Both of these results strengthen a recent result by Axenovich.
---
paper_title: WHEN DO THREE LONGEST PATHS HAVE A COMMON VERTEX?

paper_content:

It is well known that any two longest paths in a connected graph share a vertex. It is also known that there are connected graphs where 7 longest paths do not share a common vertex. It was conjectured that any three longest paths in a connected graph have a vertex in common. In this note we prove the conjecture for outerplanar graphs and give sufficient conditions for the conjecture to hold in general.
---
paper_title: Intersection of Longest Paths in a Graph

paper_content:

Abstract In 1966, Gallai asked whether every connected graph has a vertex that is common to all its longest paths. The answer to this question is negative. We prove that the answer is positive for outerplanar graphs. Another related question was raised in 1995 at the British Combinatorial Conference: Do any three longest paths in a connected graph have a vertex in common? We prove that, in a connected graph in which all non-trivial blocks are Hamiltonian, any three of its longest paths have a common vertex. Both of these results strengthen a recent result by Axenovich.
---
paper_title: Exact Numbers of Longest Cycles with Empty Intersection

paper_content:

We have proved that, for every integer??7,there is a 2-connected graph having?longest cycles the intersection of which is empty, but any set of?-1longest cycles has a non-empty intersection. This implies a new bound,c?6,on a parametercintroduced by T. Zamfirescu.
---
paper_title: Largest circuits in matroids

paper_content:

We extend to matroids Smith's Conjecture that any two distinct longest cycles of a k-connected graph meet in at least k vertices when k>=2. We generalize several known results for graphs and matroids by proving the matroid conjecture in the case that k=2.
---
paper_title: Intersections of Longest Cycles in k-Connected Graphs

paper_content:

LetGbe a connected graph, wherek?2. S. Smith conjectured that every two longest cycles ofGhave at leastkvertices in common. In this note, we show that every two longest cycles meet in at leastck3/5vertices, wherec?0.2615.
---
paper_title: Intersections of largest bonds in k-connected graphs

paper_content:

S. Smith conjectured that any two distinct longest cycles of a k-connected graph must meet in at least k vertices when k>=2. Here we provide evidence for the dual version of the Smith conjecture: if C and D are largest bonds in a k-connected graph G, then the number of components in G-(C@?D) is at least k+2-|C@?D|. Both conjectures have been proven only for small k. This article establishes a linear lower bound on the number of components of G-(C@?D) which holds for all values of k>=7. This is stronger than the best bound established to date for Smith's original conjecture.
---
paper_title: Pairs of largest circuits in 3-connected matroids

paper_content:

Abstract Smith conjectured that two distinct longest cycles of a k -connected graph meet in at least k vertices when k ⩾ 2 . We prove an extension of this conjecture for 3-connected matroids.
---
paper_title: On deletions of largest bonds in graphs

paper_content:

A well-known conjecture of Scott Smith is that any two distinct longest cycles of a k-connected graph must meet in at least k vertices when k>=2. We provide a dual version of this conjecture for two distinct largest bonds in a graph. This dual conjecture is established for k=<6.
---

Title: Intersecting longest paths and longest cycles: A survey

Section 1: Empty intersection of all longest paths
Description 1: Discuss the problem of verifying whether all longest paths in a graph intersect and present historical instances and results related to this problem including planar graphs and different levels of connectivity.

Section 2: Empty intersection of all longest cycles
Description 2: Discuss the similar problem for longest cycles, explore the existence of such graphs and present findings on smallest examples and their properties.

Section 3: Avoiding arbitrary pairs of points
Description 3: Examine the problem where certain pairs of vertices can be missed by all longest paths or cycles and summarize significant examples and results in this context.

Section 4: Non-empty intersection of all longest paths or cycles
Description 4: Provide an overview of graph families where all longest paths or cycles do intersect at a common point and describe particular graph classes and special cases.

Section 5: Intersecting three longest paths
Description 5: Investigate the condition of intersecting three longest paths, discuss known results, and outline open problems related to intersecting specific numbers of longest paths.

Section 6: Intersecting two longest paths or two longest cycles
Description 6: Review existing results and conjectures about the intersections of two longest paths or cycles in different types of graphs, including k-connected graphs, and present relevant theorems and proofs.