Abstract
Original language  Undefined 

Awarding Institution 

Supervisors/Advisors 

Award date  2 Sep 2009 
Place of Publication  Zwolle 
Publisher  
Print ISBNs  9789036528924 
DOIs  
Publication status  Published  2 Sep 2009 
Keywords
 METIS266489
 EWI15984
 IR67858
Cite this
}
Removable Edges in 4Connected Graphs. / Wu, J.
Zwolle : Wohrmann Printing Service, 2009. 130 p.Research output: Thesis › PhD Thesis  Research UT, graduation UT › Academic
TY  THES
T1  Removable Edges in 4Connected Graphs
AU  Wu, J.
PY  2009/9/2
Y1  2009/9/2
N2  Research on structural characterizations of graphs is a very popular topic in graph theory. The concepts of contractible edges and removable edges of graphs are powerful tools to study the structure of graphs and to prove properties of graphs by induction. In 1998, Yin gave a convenient method to construct 4connected graphs by using the existence of removable edges and contractible edges. He showed that a 4connected graph can be obtained from a 2cyclic graph by the following four operations: (i) adding edges, (ii) splitting vertices, (iii) adding vertices and removing edges, and (iv) extending vertices. Based on the above operations, we gave the following definition of removable edges in 4connected graphs. Definition: Let $G$ be a 4connected graph. For an edge $e$ of $G$, we perform the following operations on $G$: First, delete the edge $e$ from $G$, resulting in the graph $Ge$; Second, for each vertex $x$ of degree 3 in $Ge$, delete $x$ from $Ge$ and then completely connect the 3 neighbors of $x$ by a triangle. If multiple edges occur, we use single edges to replace them. The final resultant graph is denoted by $G \ominus e$. If $G\ominus e$ is still 4connected, then the edge $e$ is called "removable"; otherwise, $e$ is called "unremovable". In the thesis we get the following results: (1) we study how many removable edges may exist in a cycle of a 4connected graph, and we give examples to show that our results are in some sense the best possible. (2) We obtain results on removable edges in a longest cycle of a 4connected graph. We also show that for a 4connected graph $G$ of minimum degree at least 5 or girth at least 4, any edge of $G$ is removable or contractible. (3) We study the distribution of removable edges on a Hamilton cycle of a 4connected graph, and show that our results cannot be improved in some sense. (4) We prove that every 4connected graph of order at least six except 2cyclic graph with order 6 has at least $(4G+16)/7$ removable edges. We also give a structural characterization of 4connected graphs for which the lower bound is sharp. (5) We study how many removable edges there are in a spanning tree of a 4connected graph and how many removable edges exist outside a cycle of a 4connected graph. We also give examples to show that our results can not be improved in some sense.
AB  Research on structural characterizations of graphs is a very popular topic in graph theory. The concepts of contractible edges and removable edges of graphs are powerful tools to study the structure of graphs and to prove properties of graphs by induction. In 1998, Yin gave a convenient method to construct 4connected graphs by using the existence of removable edges and contractible edges. He showed that a 4connected graph can be obtained from a 2cyclic graph by the following four operations: (i) adding edges, (ii) splitting vertices, (iii) adding vertices and removing edges, and (iv) extending vertices. Based on the above operations, we gave the following definition of removable edges in 4connected graphs. Definition: Let $G$ be a 4connected graph. For an edge $e$ of $G$, we perform the following operations on $G$: First, delete the edge $e$ from $G$, resulting in the graph $Ge$; Second, for each vertex $x$ of degree 3 in $Ge$, delete $x$ from $Ge$ and then completely connect the 3 neighbors of $x$ by a triangle. If multiple edges occur, we use single edges to replace them. The final resultant graph is denoted by $G \ominus e$. If $G\ominus e$ is still 4connected, then the edge $e$ is called "removable"; otherwise, $e$ is called "unremovable". In the thesis we get the following results: (1) we study how many removable edges may exist in a cycle of a 4connected graph, and we give examples to show that our results are in some sense the best possible. (2) We obtain results on removable edges in a longest cycle of a 4connected graph. We also show that for a 4connected graph $G$ of minimum degree at least 5 or girth at least 4, any edge of $G$ is removable or contractible. (3) We study the distribution of removable edges on a Hamilton cycle of a 4connected graph, and show that our results cannot be improved in some sense. (4) We prove that every 4connected graph of order at least six except 2cyclic graph with order 6 has at least $(4G+16)/7$ removable edges. We also give a structural characterization of 4connected graphs for which the lower bound is sharp. (5) We study how many removable edges there are in a spanning tree of a 4connected graph and how many removable edges exist outside a cycle of a 4connected graph. We also give examples to show that our results can not be improved in some sense.
KW  METIS266489
KW  EWI15984
KW  IR67858
U2  10.3990/1.9789036528924
DO  10.3990/1.9789036528924
M3  PhD Thesis  Research UT, graduation UT
SN  9789036528924
PB  Wohrmann Printing Service
CY  Zwolle
ER 