Research On The Integrality Of 2-edge Connected Graphs

Many practical problems can be modeled as problems of solving the optimal solution of linear objective functions based on a system of linear constraint equations,which is linear programming.In practical problems,the constraint of the integerity of the variables should be considered,which transforms a linear programming into an integer programming.The set of all feasible solutions which satisfies the linear constraints is defined to be a polyhedron.Naturally,polyhedron plays an interesting and crucial role in combinatorial optimization.Thereby,polyhedron is a possibly useful tool for us to study integer programming.The Traveling Salesman Problem(TSP)aims to find a Hamiltonian cycle with a minimum weight in a weighted graph.The Graphical Traveling Salesman Problem(GTSP)overcomes some drawbacks of TSP,it aims to find a minimum weighted tour which traverses all vertices at least once of the graph.For the integrality of polyhedron based on GTSP,Cornuejol,Fonlupt and Naddef[7]defined a polyhedron as P(G)={x|1/2Ax≥1,x≥0},where A is the cut-edge incidence matrix of G.Furthermore,Fonlupt and Naddef[18]defined that G is TSPperfect if P(G)is the convex hull of the incidence vector of all tours in G,and then showed the characterization of TSP-perfect graphs.In addition,based on polyhedron P(G)with integrality,Ali Ridha Mahjoub([25],[26])added one more constraint requiring all variables between 0 and 1,i.e.T(G)={x|1/2Ax≥ 1,0 ≤ x≤ 1}.If T(G)fully represents all of the 2-edgeconnected spanning subgraphs in the graph G,i.e.T(G)is integer,then G is called perfect 2-edge connected(PTEC).Also he showed that any K4-minor-free graph and K3,n is PTEC.This thesis mainly focuses on the following two topics,which are both further research of the above problems.And the main results state as follows:(1)We characterize the graph structure with box-total dual integrality and establish the integral property holds by subdivision and adding multiple edges.(2)We show that G if is PTEC,then G contains no Wn as a C-minor,n≥ 3.To be specific,the integrality of T(G)holds if one edge is deleted and a cycle in G is contracted.Also,we find a minimal C-minor non-PTEC graph,that is a wheel Wn.