Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: On Extremal Graphs With No Long Paths. | On Extremal Graphs With No Long Paths Asad Ali Ali Department of Computer Science University of Mississippi University MS 38677 ali@ William Staton Department of Mathematics University of Mississippi University MS 38677 mmstaton@ 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 Erdos 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 s and at least 2S 1 vertices. Then G contains a path of at least 2S 1 vertices. The complete bipartite graphs Ks n-S with n 2S 1 show that the theorem is best possible in the sense that there exist graphs of minimum degree s 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 THE ELECTRONIC .JOURNAL OF COMBINATORICS 3 1996 R20 2 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 2 G. Suppose s 2. Then f v 1 s. If f v 1 s then every component of G v is a K . Proof To show f v 1 s first note that it is trivial for s
