關於短腳蜘蛛圖的Erdös-Sós猜想

Abstract

圖論中有關極值理論的 Erdos-Gallai 定理： n 個頂點的圖如果包含超過 (k-1)n/2 個邊，則其必包含一個 k 邊的路。根據這項結論， Erdos以及 Sos 猜測在相同的條件下，這樣的圖將會包含任何一個 k 邊的樹。蜘蛛圖，一種特別的樹，最多只能有一個頂點的度超過 2，這樣的頂點我們稱之為中心，其他的頂點的度為 1 或 2。一條從中心到度為 1 的頂點之路稱為蜘蛛圖的一隻腳。因此， 一條路即為一個一隻腳或兩隻腳的蜘蛛圖。在這篇論文中，我們將證明如果一 n 點的圖有超過 (k-1)n/2 個邊，那麼他將包含所有一隻腳長度為 5，其餘的腳長度都是 5 以下的 k 邊蜘蛛圖。另外，我們也證明如果一個 n 點的圖有超過 (k-1)n/2 個邊，且他有漢米爾頓圈，則其必包含任何 k 邊的蜘蛛圖。

A classical result on extremal graph theory is the Erd˝os-Gallai Theorem: if a graph with n vertices has more than (k−1)n/2 edges, then it contains a path of k edges. Motivated by the result, Erd˝os and S´os conjectured that under the same condition, the graph should contain every tree of k edges. A spider is a tree in which each vertex has degree 1 or 2, except for possibly one vertex, called the center of the spider. A leg of a spider is a path from the center to a vertex of degree one. Thus, a path is a spider of 1 or 2 legs. In this thesis, we prove that if a graph with n vertices has more than (k−1)n/2 edges, then it contains every k-edge spider whose legs are of length at most 4 except exactly one is of length 5. In addition, we also prove that a Hamiltonian graph with n vertices and more than (k−1)n/2 edges contains every spider of k edges.