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

Chiang Lin, Jenq Jong Lin, Tay Woei Shyu

研究成果: 書貢獻/報告類型會議論文篇章

4 引文 斯高帕斯(Scopus)

摘要

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.

原文英語
主出版物標題Combinatorics and Computer Science - 8th Franco-Japanese and 4th Franco-Chinese Conference 1995, Selected Papers
編輯Michel Deza, Reinhardt Euler, Ioannis Manoussakis
發行者Springer Verlag
頁面58-66
頁數9
ISBN(列印)3540615768, 9783540615767
DOIs
出版狀態已發佈 - 1996
對外發佈
事件4th Franco-Chinese and 8th Franco-Japanese Conference on Combinatorics and Computer Science, CCS 1995 - Brest, 法国
持續時間: 1995 7月 31995 7月 5

出版系列

名字Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
1120
ISSN(列印)0302-9743
ISSN(電子)1611-3349

會議

會議4th Franco-Chinese and 8th Franco-Japanese Conference on Combinatorics and Computer Science, CCS 1995
國家/地區法国
城市Brest
期間1995/07/031995/07/05

ASJC Scopus subject areas

  • 理論電腦科學
  • 一般電腦科學

指紋

深入研究「Complete bipartite decompositions of crowns, with applications to complete directed graphs」主題。共同形成了獨特的指紋。

引用此