The Existence Of Edge Dominating Trees In Connected Graphs

The hamiltonian problem is to find a cycle containing all vertices in a graph.It is one of the most important research topic in graph theory.For a subgraph H of G,if every vertex(or every edge)of G either lies in H or is adjacent to some vertex of H,then we call H is a/an(edge)dominating subgraph of G.In 1965,Harary and Nash-Williams proved that the line graph L(G)of graph G is hamiltonian if and only if G has a dominating closed trail.In 1986,Thomassen proposed the following famous conjecture:every 4-connected line graph is hamiltonian,which aroused widespread studies of researches,and leads to many related results.In this thesis,we consider dominating subgraphs.If a graph G has two edge disjoint trees T1,T2 such that T1 is a spanning tree and T2 is an edge dominating tree then it can be proved that G has a dominating closed trail and thus the line graph L(G)is hamiltonian.Note that a 4-connected line graph is corresponding to an essentially 4-edge connected graph.So it is significant to study the existence of edge disjoint edge dominating trees of essentially 4-edge connected graphs.In this thesis,the existence of edge disjoint edge dominating trees in a con-nected graph is studied.Some necessary conditions and sufficient conditions for the existence of two edge disjoint edge dominating trees are given.As a conse-quence,essentially 5-edge connected graph has two edge disjoint edge dominating trees under some specified conditions.Also,a class of infinite essentially 4-edge connected graphs that do not have two edge disjoint edge dominating trees is constructed.There are four chapters in this thesis:In Chapter 1,we give some related definitions and notations and then intro-duce some research progresses of Thomassen's conjecture and edge-dominating trees.Also,we list the main results of this thesis.In Chapter 2,we study the existence of edge-dominating trees of graphs.and give some sufficient conditions and some necessary conditions for graphs to have two edge-disjoint dominating trees.In Chapter 3,we study the existence of two edge disjoint edge dominating trees in essentially k-edge connected graphs.We show that essentially 5-edge con-nected graphs have two edge disjoint edge dominating trees under some specified conditions.Also we give a class of infinite essentially 4-edge connected graphs that do not,have two edge disjoint edge dominating treesIn Chapter 4,we give some further research work on this field.