Minimum degree and density of binary sequences

Brandt, Stephan; Müttel, Janina; Rautenbach, Dieter GND; Regen, Friedrich GND

For $d,k\in \mathbb{N}$ with $k\leq 2d$, let $g(d,k)$ denote the infimum density of binary sequences $(x_i)_{i\in \mathbb{Z}}\in \{0,1\}^{\mathbb{Z}}$ which satisfy the minimum degree condition $\sum\limits_{j=1}^d(x_{i+j}+x_{i-j})\geq k$ for all $i\in\mathbb{Z}$ with $x_i=1$. We reduce the problem to determine $g(d,k)$ to a combinatorial problem related to the generalized $k$-girth of a graph $G$ which is defined as the minimum order of an induced subgraph of $G$ of minimum degree at least $k$. Extending results of Kézdy and Markert, and of Bermond and Peyrat, we present a minimum mean cycle formulation which allows to determine $g(d,k)$ for small values of $d$ and $k$. For odd values of $k$ with $d+1\leq k\leq 2d$, we conjecture $g(d,k)=\frac{k^2-1}{2(dk-1)}$ and show that this holds for $k\geq 2d-3$.

Zitieren

Zitierform:

Brandt, Stephan / Müttel, Janina / Rautenbach, Dieter / et al: Minimum degree and density of binary sequences. 2009.

Zugriffsstatistik

Gesamt:
Volltextzugriffe:
Metadatenansicht:
12 Monate:
Volltextzugriffe:
Metadatenansicht:

Grafik öffnen

Rechte

Nutzung und Vervielfältigung:
Alle Rechte vorbehalten

Export