On Extremal Graphs With No Long Paths

Asad Ali Ali

Department of Computer Science University of Mississippi University, MS 38677 ali@sam.cs.olemiss.edu

William Staton Department of Mathematics University of Mississippi University, MS 38677 mmstaton@cypress.mcsr.olemiss.edu

Submitted: October 31, 1995; Accepted: June 24, 1996

Abstract

Connected graphs with minimum degree δ and at least 2δ + 1 vertices have paths with at least 2δ + 1 vertices. We provide a characterization of all such graphs which have no longer paths.

Extremal problems involving paths and cycles have been considered since the infancy of graph theory. The question which interests us here is the question of what minimum degree condition guarantees a path of a preassigned length. This question was answered by Erdös and Gallai [4] and again by Andrasfai [1]. Our formulation of their answer is

Theorem 1 Let G be a connected graph with minimum degree δ and at least 2δ + 1 vertices. Then G contains a path of at least 2δ + 1 vertices.

The complete bipartite graphs K_{δ,n−δ} with n ≥ 2δ + 1 show that the theorem is best possible in the sense that there exist graphs of minimum degree δ with no longer paths. Our purpose in this article is to characterize all such extremal graphs.

For a graph G with n vertices we define f(G) to be the number of vertices in a longest path of G, and for a vertex v of G we define f(v) to be the number of vertices in a longest path of G with initial vertex v. A set of vertices is called independent if no two of them are adjacent. By the sum H ⊕ K of two graphs we mean the graph obtained from the disjoint union of H and K by adding edges joining every vertex of H to every vertex of K. All graphs considered here are simple. Definitions of terms not explicitly given here can be found in [2].

Theorem 2 Let G be connected and v ∈ G. Suppose δ ≥ 2. Then f(v) ≥ 1 + δ. If f(v) = 1 + δ then every component of G − v is a K_{δ}.

Proof: To show f(v) ≥ 1 + δ, first note that it is trivial for δ = 2. Suppose the result is true for graphs with δ = k and let G have δ = k + 1. Let v be a vertex of G and note that G − v has minimum degree at least k. Let w be a neighbor of v. Then there is a path of k + 1 vertices in G − v beginning at w. Hence there is a path in G of k + 1 vertices in G − v beginning at w. Hence there is a path in G of k + 2 vertices beginning with v followed by w. Now suppose that f(v) = 1+δ. By Theorem 1, there are paths of 2δ +1 vertices in G. Now v must lie in the center of every such path P, or else a path from v to P followed by the longer subpath of P would result in a path of more than 1 + δ vertices beginning at v. Now consider the component or components of G − v. Each such component has at least δ vertices or else the minimum degree of G would be too small. We now claim that each component C of G − v has exactly δ vertices. Let Q be a longest path in C ∪ v starting at v. Certainly the final vertex of Q has all its neighbors on Q, forcing Q to have exactly δ + 1 vertices. Hence the final vertex of Q is adjacent to all vertices of Q. Say Q: v = v_{1}, v_{2}, ⋯, v_{1+δ}. Since v_{1+δ} is adjacent to every v_{i}, it follows that every v_{i}, i = 2, ⋯, δ + 1, is the final vertex of a longest path in C ∪ v starting at v, say v_{1}, v_{2}, ⋯, v_{i−1}, v_{δ+1}, v_{δ}, ⋯, v_{i}. Hence v_{i} has all its neighbors on Q, so the component C consists only of the vertices v_{2}, ⋯, v_{δ+1} and these are all adjacent, proving the theorem. □

Theorem 3 If G is connected and f(G) = 2δ + 1, δ ≥ 2 then

i) If G has no cut vertex and n ≥ 2δ + 2 then G = H ⊕ I where H has δ vertices and I is an independent set.

ii) If G has a cut vertex v, then G is the union of copies of K_{δ+1} with vertex v in common.

Proof:

i) Since G has no cut vertex, Theorem 4 of [3] assures us that there is a cycle of at least 2δ vertices. Let C, with vertices v_{1}, v_{2}, ⋯, v_{2δ} in cyclic order be such a cycle. First we claim the vertices not on C are independent, for if x and y are adjacent and neither is on C, then since G is connected, there is a path from x to a vertex of C. Hence there is a path which includes x, y and all 2δ vertices of C, contradicting f(G) = 2δ + 1. It follows that vertices not on C have all their neighbors on C. Since n ≥ 2δ + 2, there are at least two such vertices, say x and y. Note that the neighbors of x must be either v_{1}, v_{3}, ⋯, v_{2δ−1} or v_{2}, v_{4}, ⋯, v_{2δ}, for if x were adjacent to two consecutive vertices of C, then x could be inserted between them yielding a cycle of 2δ + 1 vertices. In this case, any edge from y to C would yield a path of length 2δ + 2. It follows that every vertex not on C has either the odd vertices or the even vertices of C as its neighbors. Suppose that x is adjacent to v_{1}, v_{3}, ⋯, v_{2δ−1} and y is adjacent to v_{2}, v_{4}, ⋯, v_{2δ}. Then v_{1}, x, v_{3}, v_{2}, y, v_{4}, v_{5}, ⋯, v_{2δ} is a path of 2δ + 2 vertices, contradicting f(G) = 2δ+1. It follows that every vertex not on C has the same neighbors, say v_{2}, v_{4}, ⋯, v_{2δ}. We now show that no two odd numbered vertices of C are adjacent. Suppose 1 ≤ i < j ≤ 2δ − 1 with i and j odd and v_{i} adjacent to v_{j}. Then the vertices x, v_{i−1}, v_{i}, v_{j}, v_{j−1}, v_{j−2}, ⋯, v_{i+1}, y, v_{j+1}, v_{j+2}, ⋯, v_{2δ}, v_{1}, v_{2}, ⋯, v_{i−2} form a path of 2δ + 2 vertices. This again contradicts f(G) = 2δ + 1. It follows that the vertices not on C along with the odd numbered vertices of C form an independent set I. Let H be the graph induced by the even numbered vertices of C. All that remains is to show that every odd numbered vertex of C is adjacent to every even numbered vertex of C. Since an odd numbered vertex of C can have no neighbor in I, the minimum degree condition forces it to be adjacent to every vertex of H.

ii) Now suppose f(G) = 2δ + 1, with δ ≥ 2, and suppose G has a cut vertex v. Note that every path beginning at v lies (except for v) entirely in a single component of G − v. Since each such component has minimum degree at least δ − 1, there are paths of δ + 1 vertices beginning with v lying in any component C. If there were a longer path from v into any such component, then attaching such a path with a path of length greater than or equal to δ + 1 vertices from another component of G − v would yield a path longer than 2δ + 1 vertices in G. It follows that f(v) = 1 + δ. By Theorem 2 each component of G − v is K_{δ}. To ensure minimum degree δ, v must be adjacent to every vertex of every component of G − v. □

Summarizing, we now know all extremal graphs, G with f(G) = 2δ + 1. The connected extremal graphs are those given in Theorem 3 along with the trivial ones with only 2δ + 1 vertices.

We noticed that the proof of Theorem 3 is easily modified to provide a characterization of non-hamiltonian graphs which barely miss satisfying Dirac’s condition. We are sure this must be known, but we have not found it in the literature. We are grateful to Arthur Hobbs [6], who made us aware of reference [5] where there are results similar to our Theorem 4.

Theorem 4 Let G be a graph with δ = k and n = 2k + 1 vertices. If G is not hamiltonian then:

i) If G has a cut vertex, then G is the union of two complete graphs K_{k+1} sharing a vertex;

ii) If G has no cut vertex, then G is H_{k} ⊕ I_{k+1} where H_{k} is a graph with k vertices and I_{k+1} is an independent set of k + 1 vertices.

Proof: Note that the degree condition and size of n force G to be connected.

i) This follows immediately from Theorem 1 and Theorem 3.

ii) In this case, by Theorem 4 of [3], there is a cycle C of 2k vertices. Let v be the vertex not on C. Say C: w_{1}, w_{2}, ⋯, w_{2k} in cyclic order. If v were adjacent to two consecutive vertices of C, G would have a hamiltonian cycle. Hence we may assume v is adjacent precisely to the w_{i} with i even. As in the proof of Theorem 3, the odd indexed w_{i} are independent. Let I_{k+1} = v, w_{1}, w_{3}, ⋯, w_{2k−1} and let H_{k} be the subgraph induced by w_{2}, w_{4}, ⋯, w_{2k}. The Theorem follows. □

References

[1] B. Andrasfai, Paths, Circuits, and Loops of Graphs, (Hungarian) Mat. Lapok 13 (1962) 95-107.

[2] G. Chartrand and L. Lesniak, Graphs and Digraphs, 2nd Edition, Wadsworth, Belmont, California, 1986.

[3] G. A. Dirac, Some Theorems on Abstract Graphs, Proc. London Math Soc. 2 (1952) 69-81.

[4] P. Erdös and T. Gallai, On Maximal Paths and Circuits of Graphs, Acta Math. Acad. Sci. Hung. 10 (1959) 337-356.

[5] L. Gordon, Hamiltonian Circuits in Graphs with Many Edges, (unpublished).

[6] A. Hobbs, Private Communication.