Genus distributions of iterated 3-wheels and 3-prisms - Poshni, Mehvish Irfan (Ars mathematica contemporanea, 2014)
The iterated 3-prism ?$Pr_3^n$? is the cartesian product ?$C_3 \Box P_n$? of a 3-cycle and an ?$n$?-vertex path. At each end of the iterated 3-prism, there is a 3-cycle whose vertices are 3-valent in ?$C_3 \Box P_n$?. The iterated 3-wheel ?$W_3^n$? is obtained by contracting one of these 3-cycles in ?$C_3 \Box P_{n+1}$? to a single vertex. Using rooted-graphs, we derive simultaneous recursions for the partitioned genus distributions of ?$W_3^n$? and a formula for the genus distribution of the graphs ?$Pr_3^n$?. A seemingly straightforward way to construct either the sequence of iterated prisms ?$Pr_3^n$? or the sequence of iterated wheels ?$W_3^n$?, would be by iterative amalgamation of a copy of ?$C_3 \Box K_2$?, such that a copy of ?$C_3$? contained in it is matched to the "newest" copy of ?$C_3$? in the growing graph. Calculating genus distributions for the sequences would then involve an excessively large set of simultaneous recurrences. To avoid this, we propose a method of iterative surgery, under which the same vertex is considered a root-vertex in all graphs of the sequence, and in which the successive calculations of genus distributions require only four simultaneous recurrences. We also prove that the genus distribution of ?$Pr_3^n$? not only dominates the genus distribution of ?$W_3^{n-1}$?, but is also dominated by the genus distribution of ?$W_3^n$?.
Keywords: 3-prism; 3-wheel; genus distribution; partitioned genus distribution; production; rooted-graph