On the decomposition of  K   n   into complete  m ‐partite graphs | Zendy

Huang Qingxue | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Premium

On the decomposition of K n into complete m ‐partite graphs

Author(s) -

Huang Qingxue

Publication year - 1991

Publication title -

journal of graph theory

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 1.164

H-Index - 54

eISSN - 1097-0118

pISSN - 0364-9024

DOI - 10.1002/jgt.3190150102

Subject(s) - combinatorics , mathematics , bipartite graph , disjoint sets , algebraic number , decomposition , enhanced data rates for gsm evolution , discrete mathematics , graph , computer science , mathematical analysis , ecology , telecommunications , biology

Graham and Pollak [3] proved that n −1 is the minimum number of edge‐disjoint complete bipartite subgraphs into which the edges of K n can be decomposed. Using a linear algebraic technique, Tverberg [2] gives a different proof of that result. We apply his technique to show that for “almost all n ,” ⌊ ( n + m −3)/( m −1) ⌋ is the minimum number of edge‐disjoint complete m ‐partite subgraphs in a decomposition of K n .

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research