Maximum Size of a Family of Pairwise Graph-Different Permutations

Original · EN

Two permutations of the vertices of a graph G are called G-different if there exists an index i such that i-th entry of the two permutations form an edge in G. We bound or determine the maximum size of a family of pairwise G-different permutations for various graphs G. We show that for all balanced bipartite graphs G of order n with minimum degree n/2 - o(n), the maximum number of pairwise G-different permutations of the vertices of G is 2⁽¹⁻ᵒ⁽¹⁾⁾ⁿ. We also present examples of bipartite graphs G with maximum degree O(n) that have this property. We explore the problem of bounding the maximum size of a family of pairwise graph-different permutations when an unlimited number of disjoint vertices is added to a given graph. We determine this exact value for the graph of 2 disjoint edges, and present some asymptotic bounds relating to this value for graphs consisting of the union of n/2 disjoint edges.