On The Structure Of Internally 4-connected Graphs

The structural characteristic of connected graphs is one of the important contents of graph theory.In this paper,we mainly characterize the structure of connected graphs and reduce connected graphs by series of contracting and deleting edges.A 3-connected graph G is called an internally 4-connected graph if each 3-separator of G does not contain edges and separates a vertice of degree 3.Let G be an internally 4-connected graph,e ∈ E(G),e is called a contractible edge if G/e is still internally 4-connected,similarly,e is called a removable edge if G\e is also internally 4-connected.An internally 4-connected graph without contractible edges is called a contraction critically internally 4-connected graph.An internally 4-connected graph G is said to be critical if it contains neither contractible edges nor removable edges.A 3-connected graph G is called a weakly 4-connected graph if there exists a component in G-T with at most two vertices for any 3-separator T.Let G be a contraction critically internally 4-connected graph,e ∈ E(G),e is called a weakly 4-contractible edge if G/e is still weakly 4-connected.On the basis of previous studies,in this paper,we mainly study the structural characteristic around the vertices of degree 3 and more than or equal to degree 5 in contraction critically internally 4-connected graphs,On this basis,the structural characteristic of the contraction critically 3-regular internally 4-connected graphs is described completely.Additionally,the lower bounds of the vertices with the degree less than 4 in critically internally 4-connected graphs are given.We also considerate the distribution of weakly 4-contractible edges in contraction critically internally 4-connected graphs and their lower bounds are given.Lastly,the construction of critically internally 4-connected graphs is also studied,eleven kinds of operations are given to reduce the critically internally 4-connected graphs,and seven of them are illustrated as necessary.The main conclusions of this paper are drawn as follows:1.Let G be a contraction critically internally 4-connected graph,x∈V3(g),then(1)There exists a quadrilateral in G containing x;(2)If there exists a quadrilateral xayb such that d(x)=d(y)=3,then the edges in E(x) and E(y)are contained in quadrilaterals.There are infinitely many examples showing that the condition of 1(2)cannot be weakened.2.G is a contraction critically 3-regular internally 4-connected graph if and only if G is either a cylindrical graph or a Mobius cylindrical graph.3.Let G be a contraction critically internally 4-connected graph,x ∈ v≥5(G),then at least one of the following conclusions holds.(1)N(x)∩V3,4(G)≠φ;(2)There exists a quadrilateral xayb in G such that d(y)=3.4.Let G be a critically internally 4-connected graph,then |V3,4(G)|≥1/5|V(G)|.5.Let G be a contraction critically internally 4-connected graph,then |EW4C(G)|≥|V3(G)|.6.Let G be a critically internally 4-connected graph,then G could be reduced by operations 2(a),2(b),4(a),4(c),4(d),5(a),5(c),5(d),5(e),6(a)or 6(b)unless G is a terrahawk,or K3,3,or Cn2,or ADW2n.Further,there are infinitely examples showing that operations 4(c),4(d),5(c),5(d),5(e),6(a),6(b)are necessary.