Smaller embeddings of partial $k$-star decompositions

Publication date: 28 September 2021

Abstract: A

k

-star is a complete bipartite graph

K_{1, k}

. For a graph

G

, a

k

-star decomposition of

G

is a set of

k

-stars in

G

whose edge sets partition the edge set of

G

. If we weaken this condition to only demand that each edge of

G

is in at most one

k

-star, then the resulting object is a partial

k

-star decomposition of

G

. An embedding of a partial

k

-star decomposition

m a t h c a l A

of a graph

G

is a partial

k

-star decomposition

m a t h c a l B

of another graph

H

such that

m a t h c a l A s u b s e t e q m a t h c a l B

and

G

is a subgraph of

H

. This paper considers the problem of when a partial

k

-star decomposition of

K_{n}

can be embedded in a

k

-star decomposition of

K_{n + s}

for a given integer

s

. We improve a result of Noble and Richardson, itself an improvement of a result of Hoffman and Roberts, by showing that any partial

k

-star decomposition of

K_{n}

can be embedded in a

k

-star decomposition of

K_{n + s}

for some

s

such that

s < f r a c 94 k

when

k

is odd and

s < (6 - 2 s q r t 2) k

when

k

is even. For general

k

, these constants cannot be improved. We also obtain stronger results subject to placing a lower bound on

n

.

This page was built for publication: Smaller embeddings of partial $k$-star decompositions