ENUMERATION OF THE DEGREE SEQUENCES OF LINE–HAMILTONIAN MULTIGRAPHS

摘要

Recently, Gu, Lai and Liang proved necessary and sufficient conditions for a given sequence of positive integers d1, d2, . . . , dn to be the degree sequence of a line– Hamiltonian multigraph. Our goal in this note is to utilize this result to prove a closed formula for the function dlh(2m), the number of degree sequences with degree sum 2m representable by line–Hamiltonian multigraphs. Indeed, we give a truly elementary proof that dlh(2m) = p(2m) ? 2 ? ? m #?1 j=0 p(j) ? ? + 1 where p(j) is the number of unrestricted integer partitions of j.