Decompositions of Complete Multipartite Graphs into Complete Graphs

Details Decompositions of Complete Multipartite Graphs into Complete Graphs Decompositions of Complete Multipartite Graphs into Complete Graphs

2011-09-15

arxiv.org/abs/1109.3508v2

Mathematics

Combinatorics

Scientific paper

Let $k\geq\ell\geq1$ and $n\geq 1$ be integers. Let $G(k,n)$ be the complete $k$-partite graph with $n$ vertices in each colour class. An $\ell$-decomposition of $G(k,n)$ is a set $X$ of copies of $K_k$ in $G(k,n)$ such that each copy of $K_\ell$ in $G(k,n)$ is a subgraph of exactly one copy of $K_k$ in $X$. This paper asks: when does $G(k,n)$ have an $\ell$-decomposition? The answer is well known for the $\ell=2$ case. In particular, $G(k,n)$ has a 2-decomposition if and only if there exists $k-2$ mutually orthogonal Latin squares of order $n$. For general $\ell$, we prove that $G(k,n)$ has an $\ell$-decomposition if and only if there are $k-\ell$ Latin cubes of dimension $\ell$ and order $n$, with an additional property that we call mutually invertible. This property is stronger than being mutually orthogonal. An $\ell$-decomposition of $G(k,n)$ is then constructed whenever no prime less than $k$ divides $n$.

Affiliated with

Also associated with

No associations

Rating

Decompositions of Complete Multipartite Graphs into Complete Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Decompositions of Complete Multipartite Graphs into Complete Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Decompositions of Complete Multipartite Graphs into Complete Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-534332