Premium
Stellar permutations of the two‐element subsets of a finite set
Author(s) -
de Caen D.
Publication year - 1998
Publication title -
journal of combinatorial designs
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.618
H-Index - 34
eISSN - 1520-6610
pISSN - 1063-8539
DOI - 10.1002/(sici)1520-6610(1998)6:5<381::aid-jcd6>3.0.co;2-b
Subject(s) - combinatorics , mathematics , star (game theory) , permutation (music) , element (criminal law) , stars , graph , discrete mathematics , physics , astrophysics , mathematical analysis , political science , law , acoustics
Let X be a finite set and denote by X (2) the set of 2‐element subsets of X . A permutation ϕ of X (2) is called stellar if, for each x in X , the image under ϕ of the star St ( x ) = {{ x , y }: x ≠ y ∈ X } is a 2‐regular graph spanning X − { x }. Several constructions of stellar permutations are given; in particular, there is a natural direct construction using self‐orthogonal Latin squares, and a simple recursive construction using linear spaces having all line sizes at least four. Apart from some intrinsic interest, stellar permutations arise in the construction of certain designs. For example, applying such a map ϕ to each of the stars St ( x ) yields a double covering of the complete graph on X by near 2‐factors. We also study stellar groups, that is groups {ϕ 1 , …, ϕ s } of permutations of X (2) such that each ϕ i is stellar (or the identity map). It is elementary to prove that s ≤ ${1 \over 2}|X|$ for any stellar group; when equality holds, one can construct an associated elation semibiplane. © 1998 John Wiley & Sons, Inc. J Combin Designs 6: 381–387, 1998