On the star arboricity of hypercubes

MaRDI QIDQ2876046zbMATH OpenFDO

Authors Negin Karisani, Narges K. Sobhani, E. S. Mahmoodian

Publication date 15 August 2014

Published in The Australasian Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1312.5698, http://ajc.maths.uq.edu.au/pdf/59/ajc_v59_p282.pdf

zbMATH Keywords

galaxies square coloring

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: A Hypercube

Q_{n}

is a graph in which the vertices are all binary vectors of length n, and two vertices are adjacent if and only if their components differ in exactly one place. A galaxy or a star forest is a union of vertex disjoint stars. The star arboricity of a graph

G

,

m s a (G)

, is the minimum number of galaxies which partition the edge set of

G

. In this paper among other results, we determine the exact values of

m s a (Q_{n})

for

n i n 2^{k} - 3, 2^{k} + 1, 2^{k} + 2, 2^{i} + 2^{j} - 4

,

i g e q j g e q 2

. We also improve the last known upper bound of

m s a (Q_{n})

and show the relation between

m s a (G)

and square coloring.

Recommendations

Cited in

(5)

This page was built for publication: On the star arboricity of hypercubes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2876046)