Cycle prefix digraphs have been proposed as an efficient model of symmetric interconnection networks for parallel architecture. It has been discovered that the cycle prefix networks have many attractive communication properties. In this paper, we det
ermine the automorphism group of the cycle prefix digraphs. We show that the automorphism group of a cycle prefix digraph is isomorphic to the symmetric group on its underlying alphabet. Our method can be applied to other classes of graphs built on alphabets including the hypercube, the Kautz graph,and the de Bruijn graph.
An alternating permutation of length $n$ is a permutation $pi=pi_1 pi_2 ... pi_n$ such that $pi_1 < pi_2 > pi_3 < pi_4 > ...$. Let $A_n$ denote set of alternating permutations of ${1,2,..., n}$, and let $A_n(sigma)$ be set of alternating permutations
in $A_n$ that avoid a pattern $sigma$. Recently, Lewis used generating trees to enumerate $A_{2n}(1234)$, $A_{2n}(2143)$ and $A_{2n+1}(2143)$, and he posed several conjectures on the Wilf-equivalence of alternating permutations avoiding certain patterns. Some of these conjectures have been proved by Bona, Xu and Yan. In this paper, we prove the two relations $|A_{2n+1}(1243)|=|A_{2n+1}(2143)|$ and $|A_{2n}(4312)|=|A_{2n}(1234)|$ as conjectured by Lewis.
We obtain a unification of two refinements of Eulers partition theorem respectively due to Bessenrodt and Glaisher. A specialization of Bessenrodts insertion algorithm for a generalization of the Andrews-Olsson partition identity is used in our combinatorial construction.
In this paper we enumerate $k$-noncrossing tangled-diagrams. A tangled-diagram is a labeled graph whose vertices are $1,...,n$ have degree $le 2$, and are arranged in increasing order in a horizontal line. Its arcs are drawn in the upper halfplane wi
th a particular notion of crossings and nestings. Our main result is the asymptotic formula for the number of $k$-noncrossing tangled-diagrams $T_{k}(n) sim c_k n^{-((k-1)^2+(k-1)/2)} (4(k-1)^2+2(k-1)+1)^n$ for some $c_k>0$.
