Bandwidth of graphs resulting from the edge clique covering problem (Q668017)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Bandwidth of graphs resulting from the edge clique covering problem |
scientific article |
Statements
Bandwidth of graphs resulting from the edge clique covering problem (English)
0 references
5 March 2019
0 references
Summary: Let \(n,k,b\) be integers with \(1 \leq k-1 \leq b \leq 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) \leq b\) and where two such vertices \(X,Y\) are joined by an edge if \(\max(X \cup Y)-\min(X \cup Y) \leq 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 \(b\geq \frac{n+k-1}{2}\), the exact bandwidth of these graphs is determined. Moreover, the bandwidth is determined asymptotically for \(b=o(n)\) and for \(b\) growing linearly in \(n\) with a factor \(\beta \in (0,1]\), 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.
0 references
bandwidth of graphs
0 references
bandwidth numbering
0 references
edge clique coverings
0 references
vertex clique coverings
0 references
\(k\)-element subsets
0 references
0 references