The minimum restricted edge-connected graph and the minimum size of graphs with a given edgedegree ?
Let G=(V(G),E(G)) G = ( V ( G ) , E ( G ) ) be a graph. Determining the minimum and/or maximum size (|E(G)| | E ( G ) | ) of graphs with some given parameters is a classic extremal problem in graph theory. For a graph G G and e=uv?E(G) e = u v ? E ( G ) , we denote d(e)=d(u)+d(v)?2 d ( e ) = d ( u ) + d ( v ) ? 2 the edgedegree of e e . In this paper, we obtain a lower bound for the minimum size of graphs with a given order n n , a given minimum degree ? ? and a given minimum edgedegree 2?+k?2 2 ? + k ? 2 . Moreover, we characterize the extremal graphs for k=0,1,2 k = 0 , 1 , 2 . As an application, we characterize some kinds of minimum restricted edge connected graphs.
edge-connectivity edgedegree minimum restricted edge connected graphs restricted edge connectivity extremal graph theory