Projects per year
Abstract
This PhD thesis consists of two parts. The first part is about edgeweightings of graphs and the second part is about applying the existence of nonseparating cycles to prove properties of graphs containing such cycles. Given a graph G and a set of numbers S ⊂R, we say that G has the Sproperty, if there there exists a function w: E(G)→ S assigning a numberfrom S toeachedge of G such that for any two neighbouring vertices u,v in G, the sum of the numbers assigned to the edges incident with u is distinct from the sum of the numbers assigned to the edges incident with v, i.e.∑e∈E(u) w(e)̸=∑e∈E(v) w(e) for any two adjacent vertices u,v in G. Such a function w is called a proper edgeweighting of G. A conjecture from 2004 by Karoński, Łuczak, and Thomason, known as the 123 Conjecture, states that any connected graph with at least 3 vertices has the{1,2,3}property. In the first part of this thesis we study problems related to this 123 Conjecture. Firstly, we characterise all 2edgeconnected bipartite graphs and all trees without the {0,1}property. We also characterise all 2connected bipartite graphs and all trees without the {a,a+2}property, where a is any odd integer. After having considered bipartite graphs we move on to consider general graphs. A listvariant of the 123 Conjecture called weightchoosability asks the following question: Given a graph G, an integer k and for each edge e in G a set Se ⊂R of k numbers, does there exist a proper edgeweighting w of G such that w(e)∈ Se for each edge e? If such an edgeweighting w exists for any assignment of kelement sets (also called lists) to the edges of G, then G is said to be kweightchoosable. We prove that any connected graph G with at least 3 vertices is (2⌈log2(∆(G))⌉+1)weightchooseable, where ∆(G) denotes the maximum degree in G, providing the first upper bound on the weightchoosability of general graphs which is logarithmic in ∆(G). We finish the chapter concerning edgeweightings by considering a variant of the Antimagic Labelling Conjecture formulated by Hartsfield and Ringel. The Antimagic Labelling Conjecture states that for any connected graph G with at least three vertices, there exists a bijection w : E(G) → {1,...,E(G)} such that for any two vertices u,v in G, the sum of the numbers assigned to the edges incident with u is distinct from the sum of the numbers assigned to the edges incident with v. We prove the following result which is a listvariant of the Antimagic Labelling Conjecture where only adjacent vertices are required to have distinct sums of incident edgeweights: For any connected graph G which is not a star and any set S ⊂R ofE(G) distinct numbers, there exists a bijection w : E(G) → S such that for any two adjacent vertices u,v in G, the sum of the numbers assigned to the edges incident with u is distinct from the sum of the numbers assigned to the edges incident with v.
These condpart of this thesis starts by considering a relaxation of the wellstudied notion of homeomorphically irreducible spanning trees which are spanning trees with no vertices of degree 2. By using the existence of nonseparating cycles in graphs of minimum degree at least 3, we prove that any graph G with minimum degree at least 3 contains a spanning tree T without a path with 3 vertices all of degree precisely 2 in T (we also say that there are no 3 consecutive vertices of degree 2 in T). After considering this relaxation of homeomorphically irreducible spanning trees we consider what is known as the 3Decomposition Conjecture formulated by Hoffmann Ostenhof. This conjecture states that the edge set of any connected cubic graph G can be partitioned into three parts, where one part induces a spanning tree in G, another part induces a collection of pairwise disjoint cycles in G and a third part induces a matching in G. Inspired by this conjecture we formulate and prove the result that the edges of any connected graph can be partitioned in to three parts, such that one part induces a spanning tree in G, another part induces a graph where all vertices have even degree in G and a third part induces a star forest in G. Finally, in the last section of this thesis, we use nonseparating cycles to prove that if G is a 2connected subcubic graph where all vertices except possibly three x,y,z have degree 3, then there are two x−y paths in G whose lengths differ by 1 or 2. We also show that under some mild additional assumptions we can allow there to be four vertices of degree 2. These results are some of the main tools in a manuscript by the author of this thesis and Martin Merker which proves that for any two integers m,k where k is odd, there exists a number N(k) such that any 3connected cubic graph with at least N(k) vertices contains a cycle whose length is congruent to m modulo k.
These condpart of this thesis starts by considering a relaxation of the wellstudied notion of homeomorphically irreducible spanning trees which are spanning trees with no vertices of degree 2. By using the existence of nonseparating cycles in graphs of minimum degree at least 3, we prove that any graph G with minimum degree at least 3 contains a spanning tree T without a path with 3 vertices all of degree precisely 2 in T (we also say that there are no 3 consecutive vertices of degree 2 in T). After considering this relaxation of homeomorphically irreducible spanning trees we consider what is known as the 3Decomposition Conjecture formulated by Hoffmann Ostenhof. This conjecture states that the edge set of any connected cubic graph G can be partitioned into three parts, where one part induces a spanning tree in G, another part induces a collection of pairwise disjoint cycles in G and a third part induces a matching in G. Inspired by this conjecture we formulate and prove the result that the edges of any connected graph can be partitioned in to three parts, such that one part induces a spanning tree in G, another part induces a graph where all vertices have even degree in G and a third part induces a star forest in G. Finally, in the last section of this thesis, we use nonseparating cycles to prove that if G is a 2connected subcubic graph where all vertices except possibly three x,y,z have degree 3, then there are two x−y paths in G whose lengths differ by 1 or 2. We also show that under some mild additional assumptions we can allow there to be four vertices of degree 2. These results are some of the main tools in a manuscript by the author of this thesis and Martin Merker which proves that for any two integers m,k where k is odd, there exists a number N(k) such that any 3connected cubic graph with at least N(k) vertices contains a cycle whose length is congruent to m modulo k.
Original language  English 

Publisher  Technical University of Denmark 

Number of pages  116 
Publication status  Published  2019 
Fingerprint Dive into the research topics of 'EdgeWeightings of Graphs and Applications of NonSeparating Cycles'. Together they form a unique fingerprint.
Projects
 1 Finished

Graph Coloring and Decomposition
Lyngsie, K. S., Thomassen, C., Gørtz, I. L., Fischer, P., BangJensen, J. & Thomason, A. G.
Technical University of Denmark
01/08/2016 → 11/09/2019
Project: PhD