|
系统科学与数学 2006
A Generalization of Dirac's K4-Subdivision Theorem
|
Abstract:
In 1960, Dirac proved that a graph $G$ on $n\geq4$ vertices with $\varepsilon(G)> 2n-3$ contains a subdivision of $K_4$. In this paper, we generalize this result by proving that a graph $G$ on $n\geq4$ vertices with $\varepsilon(G)\geq kn-\frac{(k-1)(k+2)}{2}$ where $k\geq 2$ contains a subdivision of $W_{k+1}$. Also, we give another proof of the Dirac's result using the technique of edge-switching proposed by Fan.