Permutations avoiding connected graphs


  • Norbert Sauer
  • Imed Zaguia Department of Mathematics and Computer Science Royal Military College of Canada



There is a permutation of the vertices of a tree for which no proper subtree on at least two vertices is mapped to a subtree, if and only if twice the number of its endpoints is less than or equal to the number of points of the tree;

Theorem 4.1. The following more general result follows:Let G = (V (G), E(G)) be a simple graph and let C(G) be the set of subsets

A  V (G) which induce a connected subgraph of G containing at least two vertices and let Π(G) be the set of permutations of V (G) which do not map an element of C(G) to an element of C(G). In the case where G has n vertices and at most n − 1 edges we give a necessary and sufficient condition on G so that Π(G) [SPECIAL CHARACTER]= ∅.
AMS subject classification (2000): 05C70




B. Bollobas, Extremal graph theory, Academic Press, London, 1978.

B. Bollobas and S. E. Eldridge, Packing of graphs and applications to computational complexity, J. Comb. Theory, Ser. B 25 (1978), 105-124.

D. Burns and S. Schuster, Every (p; p [SPECIAL CHARACTER] 2) graph is contained in its complement, J. Graph Theory 1 (1977), 277-279.

D. Burns and S. Schuster , Embedding (n; n[SPECIAL CHARACTER]1) graphs in their complements, Israel J. Math. 30 (1978), 313-320.

C. T. Cheng, On computing the distinguishing numbers of trees and forests, Electron. J. Combin. 31 (2006), #R11.

J. Demetrovics, M. Miyakawa, I. G. Rosenberg, D. A. Simovici, and I. Stojmenovic, Intersections of isotone clones on a nite set, Proc. 20th Internat. Symp. Multiplevalued Logic (Charlotte, NC), 1990, pp. 248-253.

J. Demetrovics and L. Ronyai, A note on intersections of isotone clones, Acta Cybernet. 10 (1992), no. 3, 217-220.

N. Eaton, A near packing of two graphs, J. Comb. Theory, Ser. B 80 (2000), 98-103.

R. Fraisse, Theory of relations, revised ed., Studies in Logic and the Foundations of Mathematics, vol. 145, North Holland, 2000.

W. Hodges, Model theory, Encyclopedia of Mathematics and its Applications, vol. 42, Cambridge University Press, London, 1994.

W. Imrich, S. Klavzar, and V. Tromov, Distinguishing innite graphs, Electron. J. Combin. 14 (2007), #R36.

C. Lafamme, L. Nguyen Van The, and N. Sauer, Distinguishing number of countable homogeneous relational structures, Electron. J. Combin. 17 (2010), #1.

F. Langer and R. Poschel., Relational systems with trivial endomorphisms and polymorphisms, J. Pure Appl. Algebra. 2 (1984), 129{142.

A. Marcus and G. Tardos, Excluded permutation matrices and the Stanley-Wilf conjecture, J. Combin. Theory, Ser. A 107 (2004), 153-160.

A. Nozaki, M. Miyakawa, G. Pogosyan, and I. Rosenberg, The number of orthogonal permutations, European J. Combin. 16 (1995), #1.

P. P. Palfy, Unary polynomial in algebra I., Algebra Universalis 18 (1984), 162-173.

I. Rival and N. Zaguia, Perpendicular orders, Discrete Math. 137 (1995), 303-313.

N. Sauer and J. Spencer, Edge disjoint placement of graphs, J. Combin. Theory Ser. B 25 (1978), 295-302.

N. Sauer and I. Zaguia, The order of the rationals has an orthogonal order with the same order type, Order 28 (2011), no. 3, 377-385.

M. Wozniak, Packing of graphs and permutations -a survey, Discrete Math. 276 (2004), 379-391.

A. Zak, Near packing of graphs, Electron. J. Combin. 20 (2013), no. 2, #P36.