Graphs with Independent Exact r r -covers for all r r

Hou Tin Chau · 2025

Read Graphs with Independent Exact r r -covers for all r r by Hou Tin Chau (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2501-05854.txt.

Introduction

Solo work in graph theory answers a standing question in a 2025 paper by Hou Tin Chau. The question, from Gray and Johnson's study of two-step transit probabilities, asks for regular graphs with a special covering property. For every r up to the degree, the graph must contain an independent exact r-cover. That is a set of vertices touching every edge exactly r times, with no two of them adjacent.

Chau constructs such graphs for every degree. Number theory trims the possibilities first: divisibility conditions limit the vertex count of any candidate, and for degrees three through six the constructions hit that minimum exactly. The building trick merges two graphs into a common covering, improving a classical construction of Angluin and Gardiner with a detour through Schreier coset graphs. The answer closes the existence question and leaves the minimal examples on the table as certificates.

Catalog record

CREATORHou Tin Chau
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE41 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-05854

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Graphs with Independent Exact r r -covers for all r r Hou Tin Chau Abstract For every natural number d d , we construct finite d d -regular simple graphs that, for every r ≤ d r\leq d , contain an independent exact r r -cover. This answers a question of Gray and Johnson that arose in their study of 2-step transit probabilities. We obtain some divisibility conditions on the order n n of graphs that for every r ≤ d r\leq d contain an independent exact r r -cover, and give constructions for d = 3 , 4 , 5 , 6 d=3,4,5,6 where the order of the graph is minimal (we deduce this minimality from our divisibility conditions). We construct these graphs as common coverings of smaller graphs. We revisit a result of Angluin and Gardiner on finite common coverings of two regular graphs of the same degree, and the result of Gross that regular graphs of even degree are Schreier coset graphs. We combine both results to provide a finite common covering of two regular graphs of the same degree, that uses fewer vertices than the construction of Angluin and Gardiner in some cases. 1 Introduction In [ 6 ] , Gray and Johnson looked at 2-step transit probabilities of random walks on 2-coloured regular graphs. Definition 1.1 (2-step transit probability, [ 6 ] Section 1) . Let G be a finite d -regular graph with an even number of vertices, and V(G)=R\sqcup B be a 2-colouring of the vertices that is balanced ( \left|R\right|=\left|B\right| ). Consider the random walk on G where each step we move to a uniformly random neighbour of the current vertex. Define P_{2}(R) as the probability that, starting from a uniformly random vertex v_{0} in R , the next two steps v_{1},v_{2} both stay in R . Similarly define P_{2}(B) . Gray and Johnson raise the question of describing the subset of [0,1]^{2} consisting of all possible values the pair (P_{2}(R),P_{2}(B)) can take. Defining the region D_{d} to be the convex hull of \{(0,0)\}\cup\left\{\left(\frac{l}{d},\frac{l^{2}}{d^{2}}\right):l\in[d-1]\right\}\cup\left\{\left(\frac{l^{2}}{d^{2}},\frac{l}{d}\right):l\in[d-1]\right\}\cup\{(1,1)\}, they showed that, for all d -regular graphs G and all balanced 2-colourings, (P_{2}(R),P_{2}(B)) lies in D_{d} ( [ 6 ] Theorem 3), and in fact if there exists a finite graph attaining all extreme points of D_{d} , then D_{d} is the closure of the set of possible pairs (P_{2}(R),P_{2}(B)) ( [ 6 ] Question 12 and Section 5). They found that the extreme points of D_{d} are closely related to independent exact r -covers. Definition 1.2 (Independent exact r -cover [ 6 ] , p.7) . Let G be a d -regular graph. For 0\leq r\leq d , an independent exact r -cover is a subset S of vertices of G such that there are no edges within S and every vertex in V(G)\setminus S is adjacent to exactly r vertices in S . (In other words, S and V\setminus S form an equitable partition with matrix \begin{pmatrix}0&d\\ r&d-r\end{pmatrix} in the sense of [ 13 ] p.159.) When \left|G\right| is finite, by double counting the number of edges between S and V\setminus S it is easy to see that any independent exact r -cover has size r\left|G\right|/(d+r) . (Note that the empty set is always an independent exact 0 -cover, so we only consider r\geq 1 in what follows.) The connection can be seen from the following example: if G has an independent exact r -cover, then (2d)\cdot G , the graph consisting of 2d disjoint copies of G , can attain the extreme point \left(\frac{d-r}{d},\quad\frac{(d-r)^{2}}{d^{2}}\right) of D_{d} , by taking the red subset to be (d-r) copies of G and (d+r) copies of S , and the blue subset to be the complement, which is (d+r) copies of G\setminus S . Gray and Johnson asked the following. Question 1.3 ( [ 6 ] , Question 13) . For each natural number d , is there a finite d -regular graph G such that, for every r\in[d] , there is an independent exact r -cover S_{r}\subset V(G) ? They described a construction for d=3 , on 40 vertices. This paper answers the question in the affirmative for general d . Theorem 1.4 . For each natural number d , there exists a finite d -regular simple graph G with an independent exact r -cover S_{r}\subset V(G) for all r\in[d] . In Section 2 we observe that it suffices to find graphs satisfying the condition for each r individually, because it is possible to combine them by taking a common covering 1 1 1 We distinguish between a “covering” of a graph (in the topological sense, Definition 2.2 ) and a “cover” of a graph (every other vertex is adjacent to a vertex from the cover). In particular we only consider the special case of “independent exact r -cover” ( Definition 1.2 ), which we always refer to by the full name. . In Section 3 we provide these smaller graphs. In Section 4 , we study how independent exact r -covers for different r intersect, leading to divisibility conditions on the graph order n which proves optimality of constructions we have for d=3,4,5,6 . 2 Graph coverings In constructing graphs satisfying Theorem 1.4 , it is convenient to allow multiple edges, self-loops, and semi-edges in the intermediate steps. We shall call them “generalized graphs” to distinguish from the simple graphs without multiple edges, loops or semi-edges. As we shall soon observe, the common covering construction for Theorem 1.4 that we obtain from these generalized graphs would still be simple. Definition 2.1 ( [ 3 ] Definition 1) . A generalized graph consists of some vertices (forming the set V ) and some darts (one half of an edge). Each dart is incident to exactly one vertex. Some darts are paired to another dart to form an edge . The dart neighbourhood \Gamma(v) of a vertex v is the set of darts incident to it, and the degree of v is the cardinality of this set. Each dart falls into one of the following three cases depending on whether/how it is paired to other darts: 1. If two darts incident to distinct vertices u,v are paired, they form an ordinary edge between u and v . 2. If two distinct darts incident to the same vertex v are paired, they form a loop (this counts as degree 2 to v ). 3. If a dart is unpaired (equivalently, paired to itself), it is a semi-edge (counts as degree 1 ). We allow multiple edges between the same pair of vertices, and also multiple loops and semi-edges on the same vertex. Semi-edges arise naturally when the two endpoints of an ordinary edge are mapped to the same vertex ( [ 3 ] Section 1.2). Definition 2.2 (Generalized graph covering, [ 3 ] Definition 4) . Let G , H be generalized graphs. A map between the sets of darts \pi\colon D(G)\to D(H) is said to be a covering map if all of the following holds: 1. \pi is surjective onto D(H) . 2. If two darts d_{1},d_{2} are incident to the same vertex v\in V(G) , then \pi(d_{1}),\pi(d_{2}) are incident to the same vertex in V(H) (which we

Read the complete text