| | |
| | |
Stat |
Members: 3667 Articles: 2'599'751 Articles rated: 2609
07 February 2025 |
|
| | | |
|
Article overview
| |
|
Bandwidth of graphs resulting from the edge clique covering problem | Konrad Engel
; Sebastian Hanisch
; | Date: |
2 May 2016 | Abstract: | Let $n,k,b$ be integers with $1 le k-1 le b le n$ and let $G_{n,k,b}$ be
the graph whose vertices are the $k$-element subsets $X$ of ${0,dots,n}$
with $max(X)-min(X) le b$ and where two such vertices $X,Y$ are joined by an
edge if $max(X cup Y) - min(X cup Y) le b$. These graphs are generated by
applying a transformation to maximal $k$-uniform hypergraphs of bandwidth $b$
that is used to reduce the (weak) edge clique covering problem to a vertex
clique covering problem. The bandwidth of $G_{n,k,b}$ is thus the largest
possible bandwidth of any transformed $k$-uniform hypergraph of bandwidth $b$.
For $bgeq frac{n+k-1}{2}$, the exact bandwidth of these graphs is determined.
For $b<frac{n+k-1}{2}$, the bandwidth is asymptotically determined in the case
of $b=o(n)$ and in the case of $b$ growing linearly in $n$ with a factor $eta
in (0,0.5]$, where for one case only bounds could be found. It is conjectured
that the upper bound of this open case is the right asymptotic value. | Source: | arXiv, 1605.0450 | Services: | Forum | Review | PDF | Favorites |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
|
| |
|
|
|