Let S be a finite set and sigma a permutation on S. The permutation sigma* on the set of 2-subsets of S is naturally induced by sigma. Suppose G is a graph and V(G), E(G) are the vertex set, the edge set, respectively. 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), (sigma 1)*(E(G)),..., (sigma(l-1))*(E(G))} have no common element, then Gis 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 first, we introduce the interspaced l-th Fibonacci and Lucas numbers. When l = 2 these numbers are the ordinary Fibonacci and Lucas numbers. It is known that the Fibonacci and Lucas numbers are rounded powers. We show that the interspaced l-th Fibonacci and Lucas numbers are also rounded powers when l = 3. Next, we show that the number of labeled graphs which are l-placeable by a given permutation is a product of the interspaced I-th Lucas numbers. Finally, using a property of the generalized binomial series, we count the number of labeled graphs of size k which are l-placeable by sigma. (C) 1996 John Wiley & Sons, Inc.