The extremal graph problem of the icosahedron |
| |
Authors: | Simonovits Miklós |
| |
Affiliation: | University L. Eötvös, Budapest, Hungary |
| |
Abstract: | P. Turán has asked the following question:Let I12 be the graph determined by the vertices and edges of an icosahedron. What is the maximum number of edges of a graph Gn of n vertices if Gn does not contain I12 as a subgraph?We shall answer this question by proving that if n is sufficiently large, then there exists only one graph having maximum number of edges among the graphs of n vertices and not containing I12. This graph Hn can be defined in the following way:Let us divide n ? 2 vertices into 3 classes each of which contains [] or vertices. Join two vertices iff they are in different classes. Join two vertices outside of these classes to each other and to every vertex of these three classes. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|