Bandwidth of graphs resulting from the edge clique covering problem

Abstract: Let

n, k, b

be integers with

1 l e k - 1 l e b l e n

and let

G_{n, k, b}

be the graph whose vertices are the

k

-element subsets

X

of

0, d o t s, n

with

m a x (X) - m i n (X) l e b

and where two such vertices

X, Y

are joined by an edge if

m a x (X c u p Y) - m i n (X c u p Y) l e 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 g e q f r a c n + k - 1 2

, the exact bandwidth of these graphs is determined. For

b < f r a c 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

, 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.

Full work available at URL: https://arxiv.org/abs/1605.00450

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

Cites Work

This page was built for publication: Bandwidth of graphs resulting from the edge clique covering problem