On independence and $k$-independence in graphs with given degree sequence

Hiller, Michaela Ursula; Triesch, Eberhard (Thesis advisor); Koster, Arie Marinus (Thesis advisor)

Aachen : RWTH Aachen University (2022)
Dissertation / PhD Thesis

Dissertation, RWTH Aachen University, 2022

Abstract

Graphs are a useful tool when it comes to representing structures and dependencies and are utilised as such in numerous disciplines of science. They appear, for example, as street networks in route planning, as representation of incompatible appointments in timetabling, and encode neighbouring countries in the proof of the famous Four Colour Theorem. It states that any map can be coloured with only four colours without two neighbouring regions sharing a colour. In physics and chemistry, graphs represent structures of molecules. In biology, they are used to study the gene regulatory networks of cells, and in social science, they model the spread of information through social networks. Mathematics provides rich theory about graphs in their own rights. One of the most researched concepts is independence in graphs, the study of subsets of non-related elements regarding a two-dimensional relation. A famous example is the eight queens problem: Place eight queens on a chess board such that they do not threaten each other. In this thesis, we examine independence in graphs that are given only by their so-called degree sequences, i.e. we have incomplete information about their structure. The question arises, which statements regarding independence hold true for all graphs corresponding to a given degree sequence. A practical example are molecular formulas in chemistry, where only the number of each type of atom is known, but not the molecule's explicit structure. A molecular formula can correspond to various molecules, each of which has different chemical properties. The independence of a molecule's graph representation is linked to the molecule's chemical stability or reactivity. In this respect, assertions about molecules with the same molecular formula are of interest. We approach independence and the generalised concept of $k$-independence for given degree sequences from a graph theoretical point of view. This thesis is structured as follows. The first chapter provides a brief overview of graph theoretical concepts used in this work, particularly with regard to degree sequences. In the second chapter, we introduce the independence number and discuss lower and upper bounds on this graph parameter. Regarding lower bounds, we focus strongly on the residue and the values it may take in certain graph classes of degree sequences. Furthermore, we examine the gap between the residue and the smallest possible independence number to assess the quality of the residue as a lower bound. Subsequently, the domination order among different elimination sequences is studied and a related conjecture by Barrus is proved. Concerning upper bounds on the independence number, the annihilation number is introduced. We disprove a theorem characterising graphs with equal independence and annihilation number, stated by Larson and Pepper, and give a new proof for restricted graph classes. The third chapter covers $k$-independence and is structured analogously to the second chapter. First, we consider lower bounds on the $k$-independence number, in particular the $k$-residue. Then upper bounds are discussed, and the annihilation number is generalised for $k$-independence. Finally, we give a summary on the contribution of this thesis and a brief outlook on possible future research.