极小n棱连通图的着色与棱数

The Coloring and Edge Number of Minimal n-Edge Connected Graph

Mader证明极小n连通图是n+1色可着的,本文证明极小n棱连通图也是n+1色可着的。并且对极小n棱连通图的棱数界进行了估计,证明了若G是p阶极小n棱连通图,则G的棱数e(G)≤n(p-1)。

Let G be a graph which contaims no loops but may contain multiple edges. Let V(G), E(G) be the vertex and edge sets of graph G respectively and λ(G) be the edge connectivity of graph G. If λ(G) =n and λ(G-e) =n- 1 for every edge e of G, then G is said to be a minimal n-edge connected graph. The minimal n-connected graph can be similarly defined. Mader proved that a minimal n-connected graph is n + 1 colorable. It is here proved that a minimal n-edge connected graph is also n+1 colorable and the bound of edge number of minimal re-edge connected grap is estimated. It is also proved that if G is a minimal n-edge connected graph with p points, then e(G)≤n(p-1), where e(G) is the edge number of graph G.