TY - GEN

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

AU - Lin, Chiang

AU - Lin, Jenq Jong

AU - Shyu, Tay Woei

N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1996.

PY - 1996

Y1 - 1996

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=21444445378&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=21444445378&partnerID=8YFLogxK

U2 - 10.1007/3-540-61576-8_74

DO - 10.1007/3-540-61576-8_74

M3 - Conference contribution

AN - SCOPUS:21444445378

SN - 3540615768

SN - 9783540615767

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

SP - 58

EP - 66

BT - Combinatorics and Computer Science - 8th Franco-Japanese and 4th Franco-Chinese Conference 1995, Selected Papers

A2 - Deza, Michel

A2 - Euler, Reinhardt

A2 - Manoussakis, Ioannis

PB - Springer Verlag

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

Y2 - 3 July 1995 through 5 July 1995

ER -