Abstract | ||
---|---|---|
Consider a graph G in which the longest path has order |V(G)|−1. We denote the number of vertices v in G such that G−v is non-traceable with tG. Gallai asked in 1966 whether, in a connected graph, the intersection of all longest paths is non-empty. Walther showed that, in general, this is not true. In a graph G in which the longest path has |V(G)|−1 vertices, the answer to Gallai’s question is positive iff tG≠0. In this article we study almost hypotraceable graphs, which constitute the extremal case tG=1. We give structural properties of these graphs, establish construction methods for connectivities 1 through 4, show that there exists a cubic 3-connected such graph of order 28, and draw connections to works of Thomassen and Gargano et al. |
Year | DOI | Venue |
---|---|---|
2018 | 10.1016/j.dam.2018.02.017 | Discrete Applied Mathematics |
Keywords | Field | DocType |
Gallai’s problem,Traceable,Hypotraceable,Almost hypotraceable | Discrete mathematics,Graph,Combinatorics,Existential quantification,Vertex (geometry),Connectivity,Longest path problem,Mathematics | Journal |
Volume | ISSN | Citations |
243 | 0166-218X | 0 |
PageRank | References | Authors |
0.34 | 15 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Gábor Wiener | 1 | 64 | 10.65 |
Carol T. Zamfirescu | 2 | 38 | 15.25 |