A polynomial space proof of the Graham-Pollak theorem

DOI10.1016/j.jcta.2007.07.006zbMath1146.05309OpenAlexW2036811773MaRDI QIDQ2427560

Sundar Vishwanathan

Publication date: 13 May 2008

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcta.2007.07.006

zbMATH Keywords

extremal combinatoricslinear algebra proofs

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Related Items (14)

Decomposing the complete \(r\)-graph ⋮ Improved bounds for the Graham-Pollak problem for hypergraphs ⋮ More on the Bipartite Decomposition of Random Graphs ⋮ A critical probability for biclique partition of \(G_{n,p}\) ⋮ Exact values and improved bounds on \(k\)-neighborly families of boxes ⋮ A counterexample to the Alon-Saks-Seymour conjecture and related problems ⋮ On the decomposition of random hypergraphs ⋮ Decomposition of Random Graphs into Complete Bipartite Graphs ⋮ Multicovering hypergraphs ⋮ Covering Complete r-Graphs with Spanning Complete r-Partite r-Graphs ⋮ Eigenvalues and clique partitions of graphs ⋮ Bounds for the Graham-Pollak theorem for hypergraphs ⋮ On decompositions of complete hypergraphs ⋮ Bipartite decomposition of random graphs

Cites Work

• Unnamed Item
• A new proof of a theorem of Graham and Pollak
• On the decomposition ofkn into complete bipartite graphs

This page was built for publication: A polynomial space proof of the Graham-Pollak theorem