Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4651225 | Discrete Mathematics | 2006 | 4 Pages |
Abstract
A tree with nn edges is stunted if its edges can be linearly ordered e1,…,ene1,…,en so that e1e1 and e2e2 share a vertex and, for all j=3,…,nj=3,…,n, edge ejej shares a vertex with at least one edge ekek satisfying 2k⩽j-12k⩽j-1. Using Alon's “Combinatorial Nullstellensatz”, a short proof is given showing that if p=2n+1p=2n+1 is prime, then every stunted tree with nn edges has a ρρ-valuation. Consequently, every stunted tree on nn edges cyclically decomposes the complete graph KpKp.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
André E. Kézdy,