Explore the vast range of titles available.

This article is intended as a survey, updating earlier surveys in the area. For completeness of the presentation of both particular questions and the general area, it also contains some material on closely related topics such as traceable, pancyclic and Hamiltonian connected graphs.

In this paper we prove the following new sufficient condition for a digraph to be Hamiltonian: ıt Let$D$be a 2-strong digraph of order$n\\geq 9$ . If$n-1$vertices of$D$have degrees at least$n+k$and the remaining vertex has degree at least$n-k-4$ , where$k$is a non-negative integer, then$D$is Hamiltonian. This is an extension of Ghouila-Houri's theorem for 2-strong digraphs and is a generalization of an early result of the author (DAN Arm. SSR (91(2):6-8, 1990). The obtained result is best possible in the sense that for$k=0$there is a digraph of order$n=8$(respectively,$n=9$ ) with the minimum degree$n-4=4$(respectively, with the minimum$n-5=4$ ) whose$n-1$vertices have degrees at least$n-1$ , but it is not Hamiltonian. We also give a new sufficient condition for a 3-strong digraph to be Hamiltonian-connected.

The longest (s,t)-path problem on supergrid graphs is known to be NP-complete. However, the complexity of this problem on supergrid graphs with or without holes is still unknown.In the past, we presented linear-time algorithms for solving the longest (s,t)-path problem on L-shaped and C-shaped supergrid graphs, which form subclasses of supergrid graphs without holes. In this paper, we will determine the complexity of the longest (s,t)-path problem on O-shaped supergrid graphs, which form a subclass of supergrid graphs with holes. These graphs are rectangular supergrid graphs with rectangular holes. It is worth noting that O-shaped supergrid graphs contain L-shaped and C-shaped supergrid graphs as subgraphs, but there is no inclusion relationship between them. We will propose a linear-time algorithm to solve the longest (s,t)-path problem on O-shaped supergrid graphs. The longest (s,t)-paths of O-shaped supergrid graphs have applications in calculating the minimum trace when printing hollow objects using computer embroidery machines and 3D printers.

A directed Toeplitz graph is a digraph with a Toeplitz adjacency matrix. In this paper we investigate the hamiltonian connectedness of directed Toeplitz graphs.

Assume that$n, \\delta ,k$are integers with$0 \\leq k < \\delta < n$ . Given a graph$G=(V,E)$with$|V|=n$ . The symbol$G-F, F \\subseteq V$ , denotes the graph with$V(G-F)=V-F$ , and$E(G-F)$obtained by$E$after deleting the edges with at least one endvertex in$F$ .$G$is called$k$ -vertex fault traceable,$k$ -vertex fault Hamiltonian, or$k$ -vertex fault Hamiltonian-connected if$G-F$remains traceable, Hamiltonian, and Hamiltonian-connected for all$F$with$0 \\leq |F| \\leq k$ , respectively. The notations$h_1(n, \\delta ,k)$ ,$h_2(n, \\delta ,k)$ , and$h_3(n, \\delta ,k)$denote the minimum number of edges required to guarantee an$n$ -vertex graph with minimum degree$\\delta (G) \\geq \\delta$to be$k$ -vertex fault traceable,$k$ -vertex fault Hamiltonian, and$k$ -vertex fault Hamiltonian-connected, respectively. In this paper, we establish a theorem which uses the degree sequence of a given graph to characterize the$k$ -vertex fault traceability/hamiltonicity/Hamiltonian-connectivity, respectively. Then we use this theorem to obtain the formulas for$h_i(n, \\delta ,k)$for$1 \\leq i \\leq 3$ , which improves and extends the known results for$k=0$ .

Spanning connectivity of graphs has been intensively investigated in the study of interconnection networks (Hsu and Lin, Graph Theory and Interconnection Networks, 2009 ). For a graph G and an integer s  > 0 and for with u ≠  v , an ( s ; u , v )-path-system of G is a subgraph H consisting of s internally disjoint ( u , v )-paths. A graph G is spanning s-connected if for any with u ≠  v , G has a spanning ( s ; u , v )-path-system. The spanning connectivity κ *( G ) of a graph G is the largest integer s such that G has a spanning ( k ; u , v )-path-system, for any integer k with 1 ≤  k ≤  s , and for any with u ≠  v . An edge counter-part of κ *( G ), defined as the supereulerian width of a graph G , has been investigated in Chen et al. (Supereulerian graphs with width s and s -collapsible graphs, 2012 ). In Catlin and Lai (Graph Theory, Combinatorics, and Applications, vol. 1, pp. 207–222, 1991 ) proved that if a graph G has 2 edge-disjoint spanning trees, and if L ( G ) is the line graph of G , then κ *( L ( G )) ≥ 2 if and only if κ ( L ( G )) ≥ 3. In this paper, we extend this result and prove that for any integer k ≥ 2, if G 0 , the core of G , has k edge-disjoint spanning trees, then κ *( L ( G )) ≥  k if and only if κ ( L ( G )) ≥ max{3, k }.

Let G be a graph on n vertices. If for any ordered set of vertices S  = { v 1 , v 2 , . . . , v k }, that is, the vertices in S appear in order of the sequence v 1 , v 2 , . . . , v k , there exists a v 1 − v k (hamiltonian) path containing S in the given order, then G is k -ordered (hamiltonian) connected. Let { u 1 , u 2 } and { u 3 , u 4 } be distinct pairs of nonadjacent vertices. When G ≠ K n and G ≠ K n - e , we define σ 4 ′ ( G ) = min { d G ( u 1 ) + d G ( u 2 ) + d G ( u 3 ) + d G ( u 4 ) } , otherwise set σ 4 ′ ( G ) = ∞ . In this paper we will present some sufficient conditions for a graph to be k -ordered connected based on σ 4 ′ ( G ) . As a main result we will show that if σ 4 ′ ( G ) ≥ 2 n + 3 k - 10 ( 4 ≤ k ≤ n + 1 2 ) , then G is k -ordered hamiltonian connected. Our outcomes generalize several related results known before.

The augmented cube ... is a variation of the hypercube ... . This paper considers the panconnectivity of ... with at most ... faulty vertices and/or edges and shows that, for any two fault-free vertices ... and ... with distance ... in ... , there exist fault-free uv-paths of every length from... to ... , where ... is the number of faulty vertices in ... . The proof is based on an inductive construction. (ProQuest: ... denotes formulae and non-USASCII text omitted)

This book presents the latest findings on one of the most intensely investigated subjects in computational mathematics--the traveling salesman problem. It sounds simple enough: given a set of cities and the cost of travel between each pair of them, the problem challenges you to find the cheapest route by which to visit all the cities and return home to where you began. Though seemingly modest, this exercise has inspired studies by mathematicians, chemists, and physicists. Teachers use it in the classroom. It has practical applications in genetics, telecommunications, and neuroscience. The authors of this book are the same pioneers who for nearly two decades have led the investigation into the traveling salesman problem. They have derived solutions to almost eighty-six thousand cities, yet a general solution to the problem has yet to be discovered. Here they describe the method and computer code they used to solve a broad range of large-scale problems, and along the way they demonstrate the interplay of applied mathematics with increasingly powerful computing platforms. They also give the fascinating history of the problem--how it developed, and why it continues to intrigue us.