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 -