Rank distributions of graphs over the field of two elements

A square matrix M represents a graph Γ if its nonzero off-diagonal entries encode the adjacencies of Γ according to a fixed vertex ordering. Over the field of two el ements, we study the distribution of ranks within the affine space of all matrices representing a particular graph. The motivating question is which graphs of or der n are represented by more matrices of rank n − 1 than of rank n. This reflects the fact that the most frequently occurring rank is not n but n − 1 in the space of all n × n matrices over F2, a property which is exceptional to F2. This thesis focuses on connected graphs that have a path or cycle as a subgraph induced on all but one vertex (called the extra vertex). The path graph Pn serves as the starting point of this study. The path graph is fundamental in the related and widely studied minimum rank problem, and provides a foundation for our later analysis of the set G P of graphs containing an induced path on all but one vertex. A main result is a characterisation of all such graphs that are represented by more matrices of rank n − 1 than rank n over F2. This is achieved by first examining the vectors in the nullspace of each matrix representing Pn. An expression for the difference α(Γ ) between rank n − 1 and rank n representations of a given graph Γ ∈ G P is determined in terms of these nullspace vectors. A recurrence is then established, expressing α(Γ ) in terms of α for graphs in G P for which the extra vertex has lower degree than in Γ . We classify all Γ ∈ G P satisfying α(Γ ) < 0 by first classifying those for which the extra vertex has degree 1, then using that to simplify and classify the degree 2 case, and continuing like this until it is shown that no such graphs exist for degree ⩾ 6. We then turn to the analogous problem for the cycle graph. We show that half of all F2-matrices representing Cn have rank n − 1, approximately one-third have rank n, and approximately one-sixth have rank n − 2 . We then investigate the set of graphs containing an induced cycle on all but one vertex, denoted by G C . Our analysis reveals essential structural contrasts between the classes G P and G C : while the degree of the extra vertex is bounded in the path case, it can be arbitrarily large in the cycle case. An infinite family of graphs called alternat ing wheel graphs demonstrate this contrast, as there exists an alternating wheel graph Γ ∈ G C with an extra vertex of any even degree d ⩾ 4 satisfying α(Γ ) < 0.

Funder

Saudi Arabian Cultural Bureau
Saudi Embassy
University of Tabuk

Publisher

University of Galway

Rights

CC BY-NC-ND

cbn

Collections

University of Galway Theses (PhD Theses)