tailieunhanh - Báo cáo toán học: " A Recurrence for Counting Graphical Partitions"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: A Recurrence for Counting Graphical Partitions. | A Recurrence for Counting Graphical Partitions Tiffany M. Barnes Carla D. Savage t Department of Computer Science North Carolina State University Raleigh North Carolina 27695-8206 Submitted February 2 1995 Accepted May 18 1995. Abstract In this paper we give a recurrence to enumerate the set G n of partitions of a positive even integer n which are the degree sequences of simple graphs. The recurrence gives rise to an algorithm to compute the number of elements of G n in time O n4 using space O n3 . This appears to be the first method for computing G n in time bounded by a polynomial in n and it has enabled us to tabulate G n for even n 220. 1 Introduction A partition of a positive integer n is a sequence of positive integers 1 K2 . i satisfying 1 K2 . Ki and 1 v2 . Ki n. Let P n denote the set of all partitions of n. P 0 contains only the empty partition A. A partition ft 2 P n is graphical if it is the degree sequence of some simple undirected graph. For example 5 4 4 3 3 1 is the degree sequence of the graph in Figure 1 a but 5 4 4 2 2 1 is not graphical. Clearly graphical partitions exist only when n is even since the sum of the degrees of the vertices of a graph is equal to twice the number of edges. Let G n denote the set of graphical partitions of n. For convenience we will call the empty partition graphical so that G 0 1. Several necessary and sufficient conditions to determine whether an integer sequence is graphical are surveyed in SH . Perhaps the best known is the following condition due to Erdos and Gallai EG Research supported by the National Science Foundation through the CRA Distributed Mentor Project 1994 Research supported in part by National Science Foundation Grant No. CCR8906500 and DIMACS 1 THE ELECTRONIC JOURNAL OF COMBINATORICS 2 1995 R11 2 a b Figure 1 a A graph with degree sequence 5 4 4 3 3 1 and b the Ferrars graph of . Erdos - Gallai A positive integer sequence 1 2 . l with 1 2 . l is graphical if and only if 1 2 . i is even and for 1 j