边临界图的新下界

New Lower Bounds for the Number of Edges of Critical Graphs

图G为简单的第二类连通图,且对G的任意边e,有x′(G-e)<x′(G),则称G是临界的.该文给出了阶为n边数为m的Δ-临界图的新下界,即m≥(3Δ+6)n/10,这里12≤Δ≤18.

A graph G is critical if it is connected of class two, and x＇（G - e） 〈 x＇（G） for any e of G. In this paper, it is proved that any △-critical graph of order n and size m satisfies： m ≥ （3△ ＋ 6）n/10, where 12 ≤ △ ≤ 18.