Local balance in graph decompositions (Q2115139)

This paper deals with equireplicate graph decomposition, a kind of graph design in which instead of edges, vertices are repeated in a same number of blocks. Here, colored loops are used as a framework to unify different types of local regularity conditions of graph decompositions such as degree-balanced and orbit-balanced decompositions, equitable block colorings, and block orderings. Let \(G\) be a finite, undirected, simple graph. A \(G\)-decomposition of a complete graph \(K_v\), where \(v\) is the number of vertices, is the partition of \(K_v\) into isomorphic copies of a subgraph \(G\). \(K_v^{\lambda}\) represents the decomposition of a complete graph \(K_v\) into copies of \(G\), where an edge is repeated exactly \(\lambda\) times. When \(G=K_k\), \(k<v\), we obtain a \((v,k,\lambda)\)-balanced incomplete block design (i.e., \((v,k,\lambda)\)-BIBD). It is also called a \(G\)-design and each copy of \(G\) is a block. Let \(G\) be a subgraph with \(n\) vertices and \(m>0\) edges and \(g\) be the gcd of the vertex degrees in \(G\). If a \(G\)-Design of \(K_v^{\lambda}\) exists, then \(2m|\lambda v(v-1)\) and \(g|\lambda v\). A \(G\)-decomposition of \(K_v^{\lambda}\) is said to be equireplicate if each vertex of \(G\) appears in equal number of copies of \(G\). The paper is divided into four sections. The first section is an introductory part, where an overview of the concepts together with the divisibility conditions and outline of the paper are given. The main result of the paper is stated here. The second section surveys some applications of the main theorem that showcase the utility of colored loops. Besides two types of decompositions, namely, degree-balanced and orbit-balanced decompositions, it deals with equitable block colorings, block orderings, equitably ordered splitting BIBDs. The third section proves the main theorem step by step using the concepts of cyclotomic construction for large prime powers, integral solutions, Wilson's construction and pairwise balanced design (PBD)-closure. The final part is on the extension of the result of the main theorem to digraphs, certain families of graphs and to hypergraphs. In order to state the main theorem, we need the following definitions: Let \(d_u\) be the number of ordinary edges incident with the vertex \(u\), \(e_{u,i}\) be the number of loops of color \(i\) at \(u\) and \(c\) be the number of different colours of loops. Let \(l_i=\Sigma_ue_{u,i}\) be the total number of loops of color \(i\) in \(G; i= 1, \ldots, c\) and \(\mu= (\mu_1,\ldots, \mu_c)\) be a tuple of non-negative integers such that \(K_v^{[\mu ;\lambda]}\) denote the multigraph on \(v\) vertices with \(k\) edges between every pair of vertices and \(l_i\) loops of color \(i\) at every vertex. This is the host graph for our decompositions. We require to count \(\mu_i=\frac{\lambda l_i(v-1)}{2m}\) loops of color \(i\) at each vertex in \(K_v^{[\mu ;\lambda]}\) for each \(i =1,\ldots, c\). With this background, the main theorem can be stated as follows: Let \(\lambda\) be a positive integer. Suppose \(G\) is a simple graph with \(n\) vertices, \(m>0\) edges, and \(l_i\) loops of color \(i\) for \(i=1, \ldots, c\). Then, there exists a \(G\)-decomposition of \(K_v^{[\mu ;\lambda]}\) for all sufficiently large integers \(v\) in such a way that it must satisfy the necessary divisibility conditions \(2m|\lambda v(v-1)\) and \(\alpha |\lambda (v-1)\), where \(\alpha \) is the least positive integer with \(\alpha (1, \frac{l_1}{2m}, \ldots, \frac{l_c}{2m}) \in \Sigma_{u \in V(G)} (d_u, e_{u,1}, \ldots, e_{u,c}) \mathbb{Z}\). Moreover, it must satisfy the multiplicities of \(\mu\) given above. As an application of the main theorem, we have the following result: Given a graph \(G\) and distinct vertices \(s,t \in V(G)\), there exists, for all sufficiently large integers \(v \equiv 1\pmod{2m}\), a \(G\)-decomposition of \(K_v\) with an \((s, t)\)-cyclic block ordering. The two corollaries on degree balanced and orbit balanced decompositions are stated respectively as follows: Let \(\lambda \ge 0\). Suppose \(H\) is a simple graph with \(n\) vertices, \(m\) edges, and degree set \(D(H)\)/vertex-orbit set \(A(H)\). Then there exists a degree-balanced \(H\)-decomposition/ orbit-balanced \(H\)-decomposition of \(K_v^\lambda\) for all sufficiently large \(v\) satisfying the necessary divisibility conditions stated in the main theorem. Moreover, degree-balanced \(H\)-decomposition has the property \(e_{u,d}= 1\) if \(\deg(u)= d\), and \(0\) otherwise and orbit-balanced \(H\)-decomposition has the property \(e_{u,a}= 1\) if \(u\) belongs to orbit \(a\), and \(0\) otherwise respectively. Equitable block colorings are closely related to `resolvability' questions. The corollary related to \(s\)-equitable block coloring is stated as: Suppose \(k\ge 2\), \(s \ge 1\) and \(\lambda \ge 0\) are given integers. There exists a \((v, k,\lambda )\)-BIBD having an \(s\)-equitable block coloring for all sufficiently large integers \(v\) satisfying \(2m| \lambda v (v-1)\) and \(s(k-1)| \lambda (v-1)\). Let \(s\) and \(t\) be distinct vertices in \(G\). A \(G\)-decomposition has an \((s, t)\)-cyclic block ordering if there is a (cyclic) ordering of its blocks so that consecutive blocks \(G_i\), \(G_{i+1}\) share the common vertex \(s\) in \(G_i\) and \(t\) in \(G_{i+1}\). The proposition regarding \((s, t)\)-cyclic block ordering is given as: Given a graph \(G\) and distinct vertices \(s,t \in V(G)\), there exists, for all sufficiently large integers \(v \equiv 1 \pmod{2m}\), a \(G\)-decomposition of \(K_v\) with an \((s,t)\)-cyclic block ordering. In order to prove the main theorem, first, we get \(v=q\), a large prime power congruent to \(1\pmod{2m}\), and any \(\lambda\) by using cyclotomic constructions. We obtain infinitely many \(G\)-designs of different orders by applying Dirichlet's theorem and `signed' \(G\)-designs under a very mild assumption \(v \ge n + 2\). This leads to \(G\)-designs with large \(\lambda^\prime>> \lambda\). An algebraic construction of Wilson's theorem stretches such a \(G\)-design on a larger number of vertices. Finally, PBD closure is invoked to get eventual periodicity of the integers \(v\) which permit one of the preceding constructions. The main theorem is extended to directed graphs with minor changes. The theorem can be applied to families of graphs, say \(\mathcal{G}\), without loops and even in certain cases, to the family of graphs with loops also. Depending on the number of colors used in the host graph, the result can be applied to hypergraphs too. This paper views \(G\)-design from the perspective of vertices. Many results are proved through various types of constructions and algebraic methods. Moreover, it heavily depends on divisibility conditions to prove the results. Certain results are extended and generalized. Applications and a few examples of the results are also given. The authors widened another area of research for interested scholars.