不含3正则子图之简单图的最大可能边数的一个上界

Upper Bound Of The Maximum Possible Numbers OF Edges In A Simple Graph Containing no 3-Regular Subgraph

Erd s和Sauer于1974年提出:“设f(p)是有p个顶点的不含3正则子图的最大可能边数、确定f(p).”本文将给出: 定理1 当P=4,5,6,7时f(p)=[(5p-9)/2] 定理2 当P≥4时f(p)≤[(p-1)]~2/4]+4 从而给出了f(p)的一个上界,部分地回答了上述问题。

In 1974 Erdos and Sauer Proposed that Let f(p) is the maximum possible number of edges in a simple graph with pertices which contains no 3-regular subgraph, find f(p). In this paper we well give; 1.f(p)=[0.5(5p-9)], when p=4,5,6,7 2.f(p)≤[0.25(p-l)~2]+4, when p≥4 Then an upper bound of f(p) is given。