Abstract
Letπ be an additive permutation of a finite integral base. It is shown that ifB is symmetric, then there is a unique additive permutationρ ofB which is compatible withπ in the sense thatπρ −1 is also an additive permutation; and that, further, ifB is asymmetric, then there is no additive permutation ofB which is compatible withπ.
Thus, in the symmetric case, there are no additively compatible sets (of permutations) forB of size greater than 3. This contrasts with the situation for completely compatible sets (equivalently, additive sequences of permutations) where for certainB compatible sets of size (resp. length) 4 or less are known, but where nothing is known of sets of greater size (resp. length). It is also noted how this result restricts the possibility of a useful multiplication theorem for the additive analogue of perfect systems of difference sets and graceful graphs.
Similar content being viewed by others
References
Abrham, J.: Perfect systems of differences sets — a survey. Ars Comb.17A, 5–36 (1984)
Abrham, J., Kotzig, A.: Generalized additive permutations of cardinality six. In: Proceedings of the Eleventh Southeastern Conference on Combinatorics, Graph Theory and Computing, Vol. 1. Congr. Numerantium28, 175–185 (1980)
Abrham, J., Kotzig, A.: Bases of additive permutations with the minimum number of negative elements. Ars Comb.13, 169–179 (1982)
Abrham, J., Kotzig, A.: Symmetric bases of additive permutations. Ars Comb.17, 49–68 (1984)
Abrham, J., Kotzig, A.: Additive permutations of an integer interval: symmetry and an estimate of their number. Ars Comb.17, 91–104 (1984)
Chang, J.J., Hsu, D.F., Rogers, D.G.: Additive variations on a graceful theme: some results on harmonious and other related graphs. In: Proceedings of the Twelfth Southeastern Conference on Combinatorics, Graph Theory and Computing, Vol. 1. Congr. Numerantium32, 181–197 (1981)
Desauliniers, H.: Sur un problème de Kotzig sur les permutations additives. Rapports de recherche de l'Université du Quebec à Trois Rivières, No. 11. 1980
Graham, R.L., Sloane, N.J.A.: On additive bases and harmonious graphs. SIAM J. Algebraic Discrete Methods4, 382–404 (1980)
Hardy, G.H., Littlewood, J.E., Polya, G.: Inequalities. Cambridge: Cambridge University Press 1934
Hsu, D.F.: Harmonious labellings of windmill graphs and related graphs. J. Graph Theory6, 85–87 (1982)
Kotzig A., Turgeon, J.: Perfect systems of difference sets and additive sequences of permutations. In: Proceedings of the Tenth Southeastern Conference on Combinatorics, Graph Theory and Computing, Vol. 2, pp. 629–636. Winnipeg: Utilitas Mathematica Publishing Inc. 1979
Kotzig A., Laufer, P.J.: When are permutations additive?. Amer. Math. Mon.85, 364–365 (1978)
Rogers, D.G.: A multiplication theorem for perfect systems of difference sets. Discrete Math. (to appear)
Rogers, D.G.: Irregular, extremal perfect systems of difference sets (to appear)
Rogers, D.G.: An arithmetic of complete permutations with constraints (to appear)
Rogers, D.G.: Automorphisms of complete permutations (to appear)
Rogers, D.G.: A parametric approach to complete permutations (to appear)
Rogers, D.G.: Some theorems on fusing graceful and other labelled graphs (to appear)
Rogers, D.G.: Harmonious windmills: perfectly additive systems (to appear)
Saito S., Hayasaka, T.: Private communication. June 1983
Turgeon, J.: An upper bound for the length of additive sequences of permutations. Utilitas Math.17, 189–196 (1980)
Turgeon, J.M.: Construction of additive sequences of permutations of arbitrary lengths. Ann. Discrete Math.12, 239–242 (1982)
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Johnson, P.D., Rogers, D.G. Compatible additive permutations of finite integral bases. Graphs and Combinatorics 2, 43–53 (1986). https://doi.org/10.1007/BF01788076
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01788076