Edge-Weightings of Graphs and Applications of Non-Separating Cycles

This PhD thesis consists of two parts. The first part is about edge-weightings of graphs and the second part is about applying the existence of non-separating 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 S-property, 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 edge-weighting of G. A conjecture from 2004 by Karoński, Łuczak, and Thomason, known as the 1-2-3 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 1-2-3 Conjecture.

Firstly, we characterise all 2-edge-connected bipartite graphs and all trees without the {0,1}-property. We also characterise all 2-connected 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 list-variant of the 1-2-3 Conjecture called weight-choosability 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 edge-weighting w of G such that w(e)∈ Se for each edge e? If such an edgeweighting w exists for any assignment of k-element sets (also called lists) to the edges of G, then G is said to be k-weight-choosable.

We prove that any connected graph G with at least 3 vertices is (2⌈log2(∆(G))⌉+1)-weight-chooseable, where ∆(G) denotes the maximum degree in G, providing the first upper bound on the weight-choosability of general graphs which is logarithmic in ∆(G). We finish the chapter concerning edge-weightings 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 list-variant of the Antimagic Labelling Conjecture where only adjacent vertices are required to have distinct sums of incident edge-weights: For any connected graph G which is not a star and any set S ⊂R of|E(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 well-studied notion of homeomorphically irreducible spanning trees which are spanning trees with no vertices of degree 2. By using the existence of non-separating 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 3-Decomposition 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 non-separating cycles to prove that if G is a 2-connected 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 3-connected cubic graph with at least N(k) vertices contains a cycle whose length is congruent to m modulo k.