Interference patterns in bijective colorings of 2-regular graphs (Q1566572): Difference between revisions

For integers \(d\) and \(n\), \(\mathcal{G}_d(n)\) denotes the set of all \(d\)-regular simple graphs with \(n\) vertices. A coloring of \(G \in \mathcal{G}_d(n)\) is a map \(f : V(G) \rightarrow \{1, 2, \ldots, n\}\). A bijective coloring (or assignment) is a coloring in which every vertex has a different color. Given a coloring \(f\) of \(G \in \mathcal{G}_d(n)\) and an integer \(\alpha\), \(0 \leq \alpha \leq n-1\), the interference number \(\mu_\alpha(G,f)\) is the number of edges \(uv\) of \(G\) such that \(\min\{|f(u) - f(v)|, n - |f(u) - f(v)|\} \leq \alpha\). For any given \(n\) and \(\alpha\), the authors determine a \(G \in \mathcal{G}_2(n)\) together with an assignment \(f\) of \(G\) such that \(\mu_\alpha(G,f)\) is as small as possible, and a \(G \in \mathcal{G}_2(n)\) such that \(\min\{\mu_\alpha(G,f) : f \text{\quad is assignment of\quad} G\}\) is as large as possible.