On the 𝑘-Independence Number and Laplacian Toughness of Graphs

Abstract

Eigenvalue interlacing and quotient matrices are crucial tools in algebraic graph theory, essential for analyzing and proving bounds for critical graph parameters. This work focuses on themes of independence number, connectivity, graph toughness, and closed walks in infinite regular trees.

Computing the 𝑘-independence number of a graph, which is the size of a largest set of vertices that are a distance greater than 𝑘 apart in the graph, is NP-complete. In other words there is no known algorithm that can find the 𝑘-independence number of a graph in a polynomial time. So bounds are important to analyse this parameter in graphs. This thesis is based on an algebraic approach which requires identifying a polynomial in order to get a good bound. Optimal polynomials have been found by other authors for the values 𝑘=1,2. In our work, we proved the optimal polynomial for 𝑘=3 and thus determining the 3-independence number for several families of graphs. For instance, we proved bounds for the Hamming graphs, which are tight for some families. We also give a construction of 3-independent sets in the Hamming graph 𝐻(𝑑,2), also known as Hypercubes. Hamming graphs play an important role in coding theory. Codes and anticodes are 𝑘-independent sets in the Hamming graph, so our bounds constrain possible codes.

Solving for these optimal polynomials require our knowledge of the number of closed walks centered on the vertices of the graph. This leads to an exploration of the number of closed walks in an infinite 𝑑-regular tree that start and end at a vertex. In the second theme of this thesis, we count closed walks in an infinite regular tree using Catalan's triangle and Borel's triangle. Specifically, we demonstrate that the number of closed walks centered on a vertex forms a polynomial in 𝑑, with coefficients aligning with the terms of the Borel triangle. These arrays of numbers, with diverse applications in mathematics, offer alternative perspectives on the underlying combinatorial structures.

Turning our attention to connectivity and toughness, we present an improved bound on vertex connectivity initially proposed by Krivelevich and Sudakov. An intimately connected concept is graph toughness, which quantifies how closely various parts of a graph are interconnected. This concept was introduced by Chvatal in 1973 and has since spurred significant research, much of it stemming from conjectures in his seminal paper. Graph toughness is linked to numerous graph properties, including Hamiltonicity, connectivity, spanning trees, graph factors, and more. In this thesis, we derived bounds on graph toughness and establish cases of a Laplacian bound on graph toughness conjectured by Haemers. Specifically, we confirm the conjecture for regular bipartite graphs, trees, and graphs with at least one leaf. We also establish the conjecture for graphs on up to 8 vertices, and some particular constructed graphs.