Back to Search
Start Over
Interference Patterns in Regular Graphs with Bijective Colorings
- Source :
- SIAM Journal on Discrete Mathematics. 15:382-402
- Publication Year :
- 2002
- Publisher :
- Society for Industrial & Applied Mathematics (SIAM), 2002.
-
Abstract
- Let ${\cal G}_d (n)$ be the set of d-regular simple graphs with n vertices, and for $G = (V,E)$ in ${\cal 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) | \} \le \alpha$. We consider two interference number problems for feasible $(n, \alpha, d)$. The first is to specify a $G \in {\cal G}_d (n)$ and an f for which the interference number is as small as possible. The second is to determine a $G \in {\cal 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 \ge 3$ and obtains partial results for the second problem for $d \ge 3$ that focus on interference-minimizing f's when G consists of disjoint copies of $K_{d+1}$.
Details
- ISSN :
- 10957146 and 08954801
- Volume :
- 15
- Database :
- OpenAIRE
- Journal :
- SIAM Journal on Discrete Mathematics
- Accession number :
- edsair.doi...........5621a3a6caee9d46b78a12bb6523d3b9