Equipartite and almost-equipartite gregarious 4-cycle systems (Q2470435): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claim: reviewed by (P1447): Item:Q175582 |
||
Property / reviewed by | |||
Property / reviewed by: Ralph J. Faudree / rank | |||
Revision as of 06:04, 10 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Equipartite and almost-equipartite gregarious 4-cycle systems |
scientific article |
Statements
Equipartite and almost-equipartite gregarious 4-cycle systems (English)
0 references
14 February 2008
0 references
A \(4\)-cycle decomposition of a complete multipartite graph is gregarious if each \(4\)-cycle in the decomposition has its vertices in different partite sets. It is proved that there is a gregarious \(4\)-cycle decomposition of the complete multipartite graph \(K_{n(m)}\) having \(n\) parts of size \(m\) if and only if \(n \geq 4\) and (i) \(m\) is even, or (ii) \(m\) is odd and \(n \equiv 1\) mod \(8\). It is also shown that if \(a\) and \(b\) are even, a gregarious \(4\)-cycle decomposition exists for \(K_{n(a), b}\), a complete multipartite graph with \(n\) parts of size \(a\) and one of size \(b\), if and only if \(n \geq 4\) and \(b \leq \lfloor a(n-1)/2 \rfloor\), or \(n = 3\) and \(a = b\). Partial results are obtained when \(a\) and \(b\) are both odd.
0 references
4-cycles
0 references
multipartite graphs, decompositions, gregarious cycles
0 references