Removable Edges in 4-Connected Graphs

J. Wu

Research output: ThesisPhD Thesis - Research UT, graduation UTAcademic

67 Downloads (Pure)

Abstract

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 4-connected graphs by using the existence of removable edges and contractible edges. He showed that a 4-connected graph can be obtained from a 2-cyclic 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 4-connected graphs. Definition: Let $G$ be a 4-connected 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 $G-e$; Second, for each vertex $x$ of degree 3 in $G-e$, delete $x$ from $G-e$ 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 4-connected, 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 4-connected 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 4-connected graph. We also show that for a 4-connected 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 4-connected graph, and show that our results cannot be improved in some sense. (4) We prove that every 4-connected graph of order at least six except 2-cyclic graph with order 6 has at least $(4|G|+16)/7$ removable edges. We also give a structural characterization of 4-connected graphs for which the lower bound is sharp. (5) We study how many removable edges there are in a spanning tree of a 4-connected graph and how many removable edges exist outside a cycle of a 4-connected graph. We also give examples to show that our results can not be improved in some sense.
Original languageUndefined
Awarding Institution
  • University of Twente
Supervisors/Advisors
  • Broersma, Hajo, Supervisor
  • Li, X., Supervisor
  • Li, Xueliang, Advisor
Award date2 Sep 2009
Place of PublicationZwolle
Publisher
Print ISBNs978-90-365-2892-4
DOIs
Publication statusPublished - 2 Sep 2009

Keywords

  • METIS-266489
  • EWI-15984
  • IR-67858

Cite this

Wu, J. (2009). Removable Edges in 4-Connected Graphs. Zwolle: Wohrmann Printing Service. https://doi.org/10.3990/1.9789036528924
Wu, J.. / Removable Edges in 4-Connected Graphs. Zwolle : Wohrmann Printing Service, 2009. 130 p.
@phdthesis{bdf49a2fd6234168ae9f474610d359e8,
title = "Removable Edges in 4-Connected Graphs",
abstract = "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 4-connected graphs by using the existence of removable edges and contractible edges. He showed that a 4-connected graph can be obtained from a 2-cyclic 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 4-connected graphs. Definition: Let $G$ be a 4-connected 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 $G-e$; Second, for each vertex $x$ of degree 3 in $G-e$, delete $x$ from $G-e$ 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 4-connected, 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 4-connected 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 4-connected graph. We also show that for a 4-connected 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 4-connected graph, and show that our results cannot be improved in some sense. (4) We prove that every 4-connected graph of order at least six except 2-cyclic graph with order 6 has at least $(4|G|+16)/7$ removable edges. We also give a structural characterization of 4-connected graphs for which the lower bound is sharp. (5) We study how many removable edges there are in a spanning tree of a 4-connected graph and how many removable edges exist outside a cycle of a 4-connected graph. We also give examples to show that our results can not be improved in some sense.",
keywords = "METIS-266489, EWI-15984, IR-67858",
author = "J. Wu",
year = "2009",
month = "9",
day = "2",
doi = "10.3990/1.9789036528924",
language = "Undefined",
isbn = "978-90-365-2892-4",
publisher = "Wohrmann Printing Service",
school = "University of Twente",

}

Removable Edges in 4-Connected Graphs. / Wu, J.

Zwolle : Wohrmann Printing Service, 2009. 130 p.

Research output: ThesisPhD Thesis - Research UT, graduation UTAcademic

TY - THES

T1 - Removable Edges in 4-Connected 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 4-connected graphs by using the existence of removable edges and contractible edges. He showed that a 4-connected graph can be obtained from a 2-cyclic 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 4-connected graphs. Definition: Let $G$ be a 4-connected 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 $G-e$; Second, for each vertex $x$ of degree 3 in $G-e$, delete $x$ from $G-e$ 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 4-connected, 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 4-connected 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 4-connected graph. We also show that for a 4-connected 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 4-connected graph, and show that our results cannot be improved in some sense. (4) We prove that every 4-connected graph of order at least six except 2-cyclic graph with order 6 has at least $(4|G|+16)/7$ removable edges. We also give a structural characterization of 4-connected graphs for which the lower bound is sharp. (5) We study how many removable edges there are in a spanning tree of a 4-connected graph and how many removable edges exist outside a cycle of a 4-connected 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 4-connected graphs by using the existence of removable edges and contractible edges. He showed that a 4-connected graph can be obtained from a 2-cyclic 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 4-connected graphs. Definition: Let $G$ be a 4-connected 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 $G-e$; Second, for each vertex $x$ of degree 3 in $G-e$, delete $x$ from $G-e$ 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 4-connected, 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 4-connected 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 4-connected graph. We also show that for a 4-connected 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 4-connected graph, and show that our results cannot be improved in some sense. (4) We prove that every 4-connected graph of order at least six except 2-cyclic graph with order 6 has at least $(4|G|+16)/7$ removable edges. We also give a structural characterization of 4-connected graphs for which the lower bound is sharp. (5) We study how many removable edges there are in a spanning tree of a 4-connected graph and how many removable edges exist outside a cycle of a 4-connected graph. We also give examples to show that our results can not be improved in some sense.

KW - METIS-266489

KW - EWI-15984

KW - IR-67858

U2 - 10.3990/1.9789036528924

DO - 10.3990/1.9789036528924

M3 - PhD Thesis - Research UT, graduation UT

SN - 978-90-365-2892-4

PB - Wohrmann Printing Service

CY - Zwolle

ER -

Wu J. Removable Edges in 4-Connected Graphs. Zwolle: Wohrmann Printing Service, 2009. 130 p. https://doi.org/10.3990/1.9789036528924