×

Interference patterns in regular graphs with bijective colorings. (English) Zbl 1007.05041

Summary: Let \({\mathcal G}_d (n)\) be the set of \(d\)-regular simple graphs with \(n\) vertices, and for \(G = (V,E)\) in \({\mathcal G}_d (n)\) let \(f: V \to \{1,2, \ldots, n \}\) be a bijective coloring of the vertices of \(G\). Also let \(\alpha\) denote an interference parameter in \(\{0,1, \ldots, n-1 \}\), and define the interference number of \(f\) with respect to \(G\) and \(\alpha\) as the number of edges \(\{u,v\}\) in \(E\) for which \(\min \{ |f(u) - f(v) |\), \(n- |f(u) - f(v) |\} \leq \alpha\). We consider two interference number problems for feasible \((n, \alpha, d)\). The first is to specify a \(G \in{\mathcal G}_d (n)\) and an \(f\) for which the interference number is as small as possible. The second is to determine a \(G \in{\mathcal G}_d (n)\) whose minimum interference number over all \(f\) is as large as possible. A previous paper completely solves both problems for \(d = 2\). The present paper solves the first problem for all \(d \geq 3\) and obtains partial results for the second problem for \(d \geq 3\) that focus on interference-minimizing \(f\)’s when \(G\) consists of disjoint copies of \(K_{d+1}\).

MSC:

05B99 Designs and configurations
05C15 Coloring of graphs and hypergraphs
05C35 Extremal problems in graph theory
Full Text: DOI