THE NUMBER OF LABELED GRAPHS PLACEABLE BY A GIVEN PERMUTATION

Let S be a finite set and sigma a permutation on S. The permutation si gma on the set of 2-subsets of S is naturally induced by sigma. Suppo se G is a graph and V(G), E(G) are the vertex set, the edge set, respe ctively. Let V(G) = S. If E(G) and sigma(E(G)), the image of E(G) by sigma have no common element, then G is said to be placeable by sigma . This notion is generalized as follows. If any two sets of {E(G), (si gma 1)(E(G)),..., (sigma(l-1))*(E(G))} have no common element, then G is said to be l-placeable by sigma. In this paper, we count the number of labeled graphs which are l-placeable by a given permutation. At fi rst, we introduce the interspaced l-th Fibonacci and Lucas numbers. Wh en l = 2 these numbers are the ordinary Fibonacci and Lucas numbers. I t is known that the Fibonacci and Lucas numbers are rounded powers. We show that the interspaced l-th Fibonacci and Lucas numbers are also r ounded powers when l = 3. Next, we show that the number of labeled gra phs which are l-placeable by a given permutation is a product of the i nterspaced I-th Lucas numbers. Finally, using a property of the genera lized binomial series, we count the number of labeled graphs of size k which are l-placeable by sigma. (C) 1996 John Wiley & Sons, Inc.