Complete bipartite decompositions of crowns, with applications to complete directed graphs

Chiang Lin, Jenq Jong Lin, Tay Woei Shyu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Citations (Scopus)

Abstract

For an integer n≥3, the crown S n 0 is defined to be the graph with vertex set {a1, a 2, ..., a n, b 1, b 2, ..., b n} and edge set {a ib 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 languageEnglish
Title of host publicationCombinatorics and Computer Science - 8th Franco-Japanese and 4th Franco-Chinese Conference 1995, Selected Papers
EditorsReinhardt Euler, Ioannis Manoussakis, Michel Deza
PublisherSpringer Verlag
Pages58-66
Number of pages9
ISBN (Print)3540615768, 9783540615767
Publication statusPublished - 1996 Jan 1
Externally publishedYes
Event4th Franco-Chinese and 8th Franco-Japanese Conference on Combinatorics and Computer Science, CCS 1995 - Brest, France
Duration: 1995 Jul 31995 Jul 5

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1120
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference4th Franco-Chinese and 8th Franco-Japanese Conference on Combinatorics and Computer Science, CCS 1995
CountryFrance
CityBrest
Period95/7/395/7/5

    Fingerprint

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Lin, C., Lin, J. J., & Shyu, T. W. (1996). Complete bipartite decompositions of crowns, with applications to complete directed graphs. In R. Euler, I. Manoussakis, & M. Deza (Eds.), Combinatorics and Computer Science - 8th Franco-Japanese and 4th Franco-Chinese Conference 1995, Selected Papers (pp. 58-66). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1120). Springer Verlag.