Article ID Journal Published Year Pages File Type
4651225 Discrete Mathematics 2006 4 Pages PDF
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
,