## Abstract

For an integer n≥3, the crown S _{n} ^{0} is defined to be the graph with vertex set {a_{1}, a _{2}, ..., a _{n}, b _{1}, b _{2}, ..., b _{n}} and edge set {a _{i}b _{j}: 1≤i,j≤n,i≠j}. We consider the decomposition of the edges of S _{n} ^{0} into the complete bipartite graphs, and obtain the following results. The minimum number of complete bipartite subgraphs needed to decompose the edges of S _{n} ^{0} is n. The crown S _{n} ^{0} has a K _{l,m}-decomposition (i.e., the edges of S _{n} ^{0} can be decomposed into subgraphs isomorphic to K _{l,m}) if n=λlm+1 for some positive integers λ, l, m. Furthermore, the l-part and m-part of each member in this decomposition can be required to be contained in {a _{1}, a _{2}, ..., a _{n}} and {b _{1},b _{2}, ..., b _{n}}, respectively. Every minimum complete bipartite decomposition of S _{n} ^{0} is trivial if and only ifn=p+1 where p is prime (a complete bipartite decomposition of S _{n} ^{0} that uses the minimum number of complete bipartite subgraphs is called a minimum complete bipartite decomposition of S _{n} ^{0} and a complete bipartite decomposition of S _{n} ^{0} is said to be trivial if it consists of either n maximal stars with respective centers a _{1}, a _{2}, ..., a _{n}, or n maximal stars with respective centers b _{1}, b _{2}, ..., b _{n}). The above results have applications to the directed complete bipartite decomposition of the complete directed graphs.

Original language | English |
---|---|

Title of host publication | Combinatorics and Computer Science - 8th Franco-Japanese and 4th Franco-Chinese Conference 1995, Selected Papers |

Editors | Reinhardt Euler, Ioannis Manoussakis, Michel Deza |

Publisher | Springer Verlag |

Pages | 58-66 |

Number of pages | 9 |

ISBN (Print) | 3540615768, 9783540615767 |

Publication status | Published - 1996 Jan 1 |

Externally published | Yes |

Event | 4th Franco-Chinese and 8th Franco-Japanese Conference on Combinatorics and Computer Science, CCS 1995 - Brest, France Duration: 1995 Jul 3 → 1995 Jul 5 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 1120 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 4th Franco-Chinese and 8th Franco-Japanese Conference on Combinatorics and Computer Science, CCS 1995 |
---|---|

Country | France |

City | Brest |

Period | 1995/07/03 → 1995/07/05 |

## ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)