The Edge Connectivity Of Middle P₂-graphs

The edge-connectivity in graph theory is an important measure for the networks,which can accurately characterize the fault tolerance of systems with few processor. The results are useful tool to study the topological structure of networks.In 1932,Whitney[1] proposed the definition of line graphs,and obtained many beau-tiful results.Later, Path graphs were introduced by Broersma and Hoede [2] as a gener-alization of line graphs. The Pk-path graph Pk(G) is the graph whose vertex set is all paths of length k in G. Two vertices are adjacent if and only if the intersection of the corresponding paths forms a path of length k-1,and their union forms either a cycle or a path of length k+1 in G. Clearly, P1(G) is a line graph of G, for k=1.The Middle graph M(G) of G [15] is the graph whose vertex set is V(G) U E(G),and two vertices x and y are adjacent if and only if at least one of x and y is an edge of G, and they are adjacent or incident in G.In this thesis,we give the definition of Middle Pk-graph of G by generalizing the concept of Middle graph.The Middle Pk-graph Mk(G) of G is the graph whose vertex set is V(Mk(G))= (V(G)∪V(Pk(G))) and edge set is E(Mk(G))=(E(Pk(G))∪Ek),where Ek={(v,p): p∈V(Pk(G)),v is an end vertex of p in G}.By the above definition,we have:M1(G)=M(G),when k=1 and M2(G)=(V(G)∪V(P2(G)),E(P2(G))∪E2), when k= 2.A graph is Eulerian if it has a closed trail containing all edges.An even [odd] graph is a graph with vertex degrees all even [odd].In this thesis,we prove that:(1)Let G be a connected graph and|V(G)|≥3.Ifδ(G)≥2,then P2(G) and M2(G) are both connected andλ(M2(G))≥2.(2) Let G be a connected graph.Ifδ(G)≥3,thenλ(M2(G))≥2δ(G).(3) Let G be a connected graph.If G is Eulerian, then M2(G) is Eulerian.(4) Let G and M2(G) are both connected.If M2(G) is Eulerian, then G is an even graph or an odd graph.