Hamilton path decompositions of complete multipartite graphs
Darryn BryantHao Chuien HangSarada Herke
所有作者
Darryn BryantHao Chuien HangSarada Herke
文献摘要
We prove that a complete multipartite graph K with n>1 vertices and m
edges can be decomposed into edge-disjoint Hamilton paths if and only if $\frac
m{n-1}isanintegerandthemaximumdegreeofKisatmost\frac
{2m}{n-1}$.