ARS MATHEMATICA CONTEMPORANEA
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 7 (2014) 423-440
Genus distributions of iterated 3-wheels and
3-prisms
Mehvish I. Poshni, Imran F. Khan
PUCIT, University of the Punjab, Lahore 54000, Pakistan
Jonathan L. Gross Department of Computer Science, Columbia University, New York, NY 10027, USA.
Received 19 September 2012, accepted 22 October 2013, published online 26 December 2013
The iterated 3-prism Pr% is the cartesian product C3mPn 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 C3DPn. The iterated 3-wheel W3 is obtained by contracting one of these 3-cycles in C3DPn+i to a single vertex. Using rooted-graphs, we derive simultaneous recursions for the partitioned genus distributions of W3 and a formula for the genus distribution of the graphs Pr%. A seemingly straightforward way to construct either the sequence of iterated prisms Pr% or the sequence of iterated wheels would be by iterative amalgamation of a copy of C3nK2, such that a copy of C3 contained in it is matched to the "newest" copy of C3 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% not only dominates the genus distribution of W%-1, but is also dominated by the genus distribution of .
Keywords: genus distribution, rooted-graph, production, partitioned genus distribution, 3-prism, 3-wheel.
Math. Subj. Class.: 05C10
E-mail address: mehvish.irfan@pucit.edu.pk (Mehvish I. Poshni), imran.farid@pucit.edu.pk (Imran F. Khan)gross@cs.columbia.edu (Jonathan L. Gross)
Abstract
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
402
Ars Math. Contemp. 7 (2014) 379-424
1 Introduction
In this paper, the rooted-graphs method is used for computing genus distributions of the iterated 3-prism Prg\ i.e., the cartesian product C3üPn of the 3-cycle C3 and the path graph Pn. This is made possible by reducing the problem of computing genus distributions of Prnn to the problem of computing genus distributions of the iterated 3-wheel W3n-1 obtained by contracting one of two cubic 3-cycles in Prn, for n > 2, to a single vertex. Figure 1.1 shows the iterated 3-prisms Prn+1 and the iterated 3-wheels W3 for n =1, 2, and 3.
Figure 1.1: Iterated 3-prisms Prn+1 and iterated 3-wheels for n = 1,2,3.
The motivation for obtaining genus distributions of iterated 3-prisms via genus distributions of iterated 3-wheels stems from the observation that subdividing the edges incident with a particular vertex of the iterated 3-wheel and adding an edge between the subdivision vertices yields the iterated 3-prism, as shown in Figure 1.2.
Figure 1.2: Obtaining the iterated 3-prism Prf from the iterated 3-wheel W3.
Familiarity with fundamentals in topological graph theory is assumed (see [7] or [22]). Graphs are assumed to be connected and graph embeddings are assumed to be 2-cellular. The genus distribution of a graph is the sequence of the number of its 2-cellular embed-dings in each orientable surface. It may be written as a sequence g0, g1, g2, • • • or as a polynomial g0 + g1x1 + g2x2 + • • • .A closed walk along the boundary of a face is known as a face-boundary walk. We abbreviate a face-boundary walk as fb-walk. An open sub-walk of an fb-walk is known as a strand and a minimal open sub-walk of an fb-walk that starts and ends at a vertex v, with no intermediate occurrences of v, is called a v-strand.
A single-vertex-rooted graph, or more simply a single-rooted graph, is a graph in which any vertex is designated a root-vertex. The notation (G, v) is used to signify that the vertex v serves as the root-vertex of the graph G. Analogously, a double-rooted graph is a graph with any two vertices designated as roots. The rooted-graphs method has also been
M. I. Poshni et al.: Genus distributions of iterated 3-wheels and 3-prisms	425
used with edges and sub-graphs serving as roots. In this paper, however, we assume that any reference to a root is a reference to a root-vertex.
The problem of computing genus distributions was first introduced in [5]. Since then genus distributions have been computed for various families of graphs using different techniques (see, for example, [15], [16], [9], [1], [10], [17], [12], [18], [11], [2], [20], [19], [21], and [3]). More recently, techniques for finding partitioned genus distribution of rooted-graphs have been developed in [6], [4], [13], [8] and [14] for calculating genus distributions of large classes of graphs. In contradistinction to all previous results, where each graph operation results in one or more new root-vertices in the resulting graph, this paper has the novel feature that the same root-vertex is retained as a root for each graph Wn, for successive values of n.
In §2, we introduce some machinery for obtaining recurrences for partitioned genus distribution of the graph W% in terms of the partials of W^-1. In §3, a formula for the genus distribution of PrJ is derived in terms of the partitioned genus distribution of W^-1. It is also shown that genus distribution of Pr3 dominates the genus distribution of W^-1 and is dominated by the genus distribution of Wg\
2 Genus distributions of iterated 3-wheels 2.1 Rim-insertion
Let (W3n, v) be a rooted-graph with root-vertex v. The graph (W^+1, v) can be obtained from (W3n, v) by performing the following graph operations:
(i)	each of the three edges incident on v is subdivided.
(ii)	the subdivision vertices are made pairwise adjacent by adding three new edges.
The vertex v is retained as the root-vertex for W^+1. Thus, W^+1 has three more vertices and six more edges than the graph W^. This is illustrated in Figure 2.1. We refer to this operation as rim-insertion.
Figure 2.1: Applying rim-insertion to iteratively, for n = 1 and 2.
2.2 Partials and partitioned genus distribution
In any given embedding i of the graph (W£, v), the trivalent root-vertex v occurs exactly thrice in the fb-walks of the regions of the embedding, giving rise to three v-strands. Based
426
ArsMath. Contemp. 7(2014)405-421
on how the three v-strands stand in relation to each other, the vertex v may occur once or twice or thrice in the same fb-walk. As illustrated in Figure 2.2, the embeddings of (WJ", v) on the surface Si can be classified into the following four types:
•	Type a: root-vertex v occurs in three distinct fb-walks.
•	Type b: root-vertex v occurs twice in one fb-walk and once in another fb-walk.
•	Types c' and c'': root-vertex v occurs thrice in the same fb-walk. The two ways in which this can happen are shown in Figure 2.2.
These four types are referred to as partial-types. The number of embeddings of the graph W3n of partial-types a, b, c', and c" on the surface Si are known as partials and are denoted
by ai, bi, ci and ci', respectively.
The partitioned genus distribution of the graph Wg is the set of sequences of its partials for each orientable surface. Clearly, summing the partials for each orientable surface would yield the genus distribution of the graph. Like the genus distribution sequence, the partitioned genus distribution sequence may also be written as a polynomial.
Example 2.1. The partitioned genus distribution of the 3-wheel Wg is 2a0 + 12b1 + 2c!x which implies that its genus distribution is 2 + 14x.
2.3 Productions for the rim-insertion operation
It is evident that for each embedding iw of the graph Wg, the rim-insertion operation induces (3!)3 = 216 embeddings of WJ+1 whose rotation systems are consistent with the rotation system of iw. By handling all 216 possibilities collectively with the rim-insertion operation, rather than, say, by inserting the edges of a new rim one at a time, we are able to keep the number of simultaneous recursions (see Corollary 2.4) down to four. This simplifies the calculation of partitioned genus distributions for W3, as demonstrated in §2.4.
A production for rim-insertion classifies the 216 embeddings of WJ+1, produced as a consequence of applying rim-insertion to an embedding of W^, into their respective partial-types. The productions for each of the four partial-types are given in Theorem 2.3. A production is symbolically written as:
Figure 2.2: Partial-types a, b, c' and c'' from left to right.
y ranges over all sub-partial types with Ae{0,1,2}
M. I. Poshni et al.: Genus distributions of iterated 3-wheels and 3-prisms
427
Each such production can be construed as signifying that any embedding of W3n of partial-type x and genus i, as a result of rim-insertion, produces exactly aVi+A embeddings of	having partial-type y and genus i + A. For each such production, the sum of all
coefficients aVi+A on the right-hand-side is 216.
We refer to the left-hand-side of a production as the antecedent and the right-hand-side of a production as the consequent.
Remark 2.2. If instead of the rim-insertion operation, the edges of a new rim are added one at a time, the rim-insertion operation breaks into three stages. The first stage consists of joining two of the three subdivision vertices, inserted on the edges incident on the root, resulting in a 4-fold increase in the number of embeddings. The second stage consists of a subsequent 6-fold increase in the number of embeddings from joining a trivalent vertex to a bivalent vertex, and the third stage consists of a further 9-fold increase from joining two trivalent vertices. Such a breakdown of the rim-insertion operation into three distinct operations has the disadvantage that a different definition of production has to be used for each of these three operations, leading to three sets of productions and three sets of simultaneous recursions corresponding to these sets of productions. It would require a considerable amount of effort to reduce the three sets of simultaneous recursions to the single set of simultaneous recursions of Corollary 2.4.
Theorem 2.3 gives the complete set of productions for rim-insertion with the graphs Wn and Wn+1 omitted from the antecedent and consequent, respectively, for greater readability.
Theorem 2.3. When an embedding of the single-rooted graph (Wg, v) undergoes rim-insertion it produces embeddings of the resultant graph (W^+1,v) whose partial-types and genera are specified by the following productions:
ai —> ai + 42ai+i + 15bi+i + 1176i+2 + 30ci+2 + 11ci+2	(2.1)
bi 6ai + 54am + 72bi+i + 54ci+2 + 6ci+1 + 24ci+2	(2.2)
ci 30ai + 15bi + 117bi+1 + ci + 42ci+1 + 11^+1	(2.3)
i+1
ci 27ai + 162bi+1 +27c'	(2.4)
Proof. Subdividing the edges incident on the root-vertex of Wg does not change the partial-type of the resultant graph embedding. All fb-walks other than the ones containing the root-vertex remain unchanged. The fb-walks incident on the root-vertex are changed only by the introduction of occurrences of the subdivision vertices. Similarly, the edge-ends of the three new edges (added as part of the rim-insertion) are inserted into faces incident on the root-vertex. Consequently, only the fb-walks incident on the root-vertex undergo any change.
Each fb-walk incident on the root-vertex can be viewed as being constituted from strands passing over the root and over one or more subdivision vertices. The addition of the three new edges in effect breaks an fb-walk into strands which recombine with each other and with traversals of the new edges to generate new fb-walks, as shown in Figure 2.3 for partial-type a. Figure 2.3 does not account exhaustively for all 216 embeddings and is meant only as an illustration of the point in fact. The embedding types produced in the cases shown are of types a, b, c', and c" from left to right, respectively. Notice, that in the first case the three fb-walks incident on the root break into strands that recombine to
402
Ars Math. Contemp. 7 (2014) 379-428
produce three additional faces. Since there are three additional vertices, six more edges and three more faces, it follows by the Euler-polyhedral equation that the genus of the resulting graph embedding is identical to the genus of the original graph embedding prior to rim-insertion. In the remaining three cases shown, there is one less face resulting in a graph embedding with a genus increment of two. This accounts for the four terms aj, bi+2, c'i+2, and
cj+2 in the consequent of Production (2.1). Derivations of the remaining contributions to the consequent are similar, and the number of drawings needed, if one proceeds by hand, can be reduced by consideration of symmetries.
Figure 2.3: Changes in fb-walks for partial-type a.
The proof for Productions (2.1)-(2.4) consists of running the above-mentioned algorithm based on Heffter-Edmonds face-tracing for each partial-type. In doing this manually, symmetries are useful for expediting the derivations. Figure 2.4 illustrates one such scenario. The empty box covering one of the subdivision vertices represents an unknown rotation. For the remaining two vertices, fixing the rotation at one and varying it in all six ways on the other breaks the fb-walks into the four strands distinguished by the color and graphic indicated in the legend to the left of the figure.
Figure 2.4: Similar embedding types produced from symmetries.
In the upper half of the figure, the placement of the strands is such that for each way of choosing the unknown rotation, represented by the empty box, the same type of embedding will be produced for all three models. Similar is the case for the three models shown at the bottom. Such symmetries can simplify the derivation of the Productions (2.1)-(2.4).
M. I. Poshni et al.: Genus distributions of iterated 3-wheels and 3-prisms
429
To organize the efforts for deriving the 216 partial-types in the consequent of the productions, we consider the derivation of Production (2.4). We regard the rotations at the vertices v^ v2 and v3 in the inserted rim of the embedding model of Figure 2.5 as the canonical set of rotations.
Figure 2.5: Set of canonical rotations at vertices v1, v2 and v3 in the rim.
Then the remaining partial-types in the consequent of Production (2.4) can be obtained according to three principles:
(i)	Two of the three rotations at vi, v2, v3 are fixed as in the canonical set. Varying the rotation at the third vertex in five ways gives 5 embeddings: 2 of type ai and 3 of type bi+1. By symmetry, there are three ways to choose such a vertex. This yields a total of 15 (= 3 x 5) embeddings: 6 (= 3 x 2) of type ai and 9 (= 3 x 3) of type
bi+1.
(ii)	Fix the rotation on v1 as in the canonical set. There are 25 ways of varying the non-canonical rotations at the vertices v2 and v3. There are five ways of fixing a non-canonical rotation at v2 giving rise to five cases:
(a)	For three of these five cases, the five non-canonical rotations at v3 produce 5 embeddings of type bi+1 giving a total of 15 (=3 x 5) embeddings of type
bi+i.
(b)	For the remaining two of the five cases, the five non-canonical rotations at v3 produce 2 embeddings of type ai and 3 of type bi+1 giving a total of 4 (=2 x 2) embeddings of type ai and 6 (=2 x 3) embeddings of type bi+1.
(c)	This accounts for the 25 embeddings: 4 of type ai and 21 (= 15 + 6) of type
bi+1.
By symmetry, the same is true if the canonical rotation is retained on vertex v2 or v3 instead of v1. This gives a total of 75 embeddings: 12 (= 3 x 4) of type ai and
63 (= 3 x 21) of type bi+1.
(iii)	If none of the rotations at the vertices in the rim is a canonical rotation, then there are a total of 125 embeddings. There are twenty five ways of fixing the non-canonical rotations at v2 and v3.
(a) For four of these twenty five cases, varying the non-canonical rotations at v1 produces 2 embeddings of types ai and 3 of type bi+1 giving a total of 8 (= 4 x 2) embeddings of type ai and 12 (=4 x 3) embeddings of type bi+1.
402
Ars Math. Contemp. 7 (2014) 379-430
(b)	For nine of the twenty five cases, varying the non-canonical rotations at v1 produces 2 embeddings of type b'+1 and 3 embeddings of type c'+1 giving a total of 18 (=9 x 2) embeddings of type bi+1 and 27 (=9 x 3) embeddings of type
c'+i.
(c)	In the remaining twelve of the twenty five cases, varying the non-canonical rotations at v1 produces 5 embeddings of type bi+1 for a total of 60 (= 12 x 5) embeddings of type bi+1.
(d)	This gives a total of 125 embeddings: 8 of type a', 90 (= 12 + 18 + 60) of type bi+1 and 27 of type c'+1.
In summary the following types of embeddings are accounted for:
•	One embedding of type a' for the canonical set of rotations in Figure 2.5.
•	From principle (i) 6 embeddings of type a' and 9 embeddings of type bi+1.
•	From principle (ii) 12 embeddings of type a' and 63 embeddings of type bi+1.
•	From principle (iii) 8 embeddings of type a', 90 embeddings of type bi+1 and 27 embeddings of type c'+1.
The sum of the number of embeddings for each partial-type obtained above accounts for the consequent of Production (2.4). The proofs for the remaining productions can be organized along similar lines. For brevity, detailed proofs of the given productions are omitted. □
Corollary 2.4. Given the partitioned genus distribution of single-rooted graph (W3\ v), the partitioned genus distribution of the graph (WJ+1,v) is specified by the following recurrences that express the partials of WJ+1 as a sum ofpartials of W31: NB: The partials on the right-hand-sides are for the graph W3n.
a'[W3n+1 ]	= a' + 42a'-1 + 6b' + 54b'_1 + 30c' + 27c''	(2.5)
b'[W3n+1 ]	= 15a'_ 1 + 117a'-2 + 72b'_1 + 15c' + 117c'_1 + 162c''_1	(2.6)
c' [W3n+1 ]	= 30a'_2 + 54b'_2 + 6b'_1 + c' + 42c'_1 + 27c'_1	(2.7)
c''[W3n+1 ]	= 11a'_2 + 24b'_2 + 11c'_1	(2.8)
Proof. The terms a'[W3l+1] + 42a'+1[W3l+1] in the consequent of Production (2.1) contribute to the terms a^W^] + 42a'_1[W3'] in Equation (2.5). Similarly, the terms 6a'[W3n+1] + 54a'+1 [W3n+1] in the consequent of Production (2.2) contribute to all the terms in Equation (2.5) containing partial-type b, and finally the terms 30a'[W^1] and 27a'[W3n+1] in the consequents of Productions (2.3) and (2.4), respectively, contribute to the terms in Equation (2.5) containing partial-types c' and c'', respectively.
Recurrences (2.6)-(2.8) can also be obtained by transposing the productions in a similar manner.	□
The reader may observe the similarity between Equations (2.5) and (2.7). In fact, as the following result shows a'_1 [W^] = c' [W^]. Corollaries 2.2 and 2.7 are given for the interested reader and will not be used later.
M. I. Poshni et al.: Genus distributions of iterated 3-wheels and 3-prisms
431
Corollary 2.5. The partial a [W?] = ci+1 [W?] for all values of i and n.
Proof. By the Heffter-Edmonds face-tracing algorithm, the partitioned genus distribution of the graph W31 is 2a0 + 12b1 + 2c1. The result is clearly true for the base case. Assume that the proposition is true for W3k for all values of i and some k > 1. Then, by inductive hypothesis, Equation (2.5) becomes
a [W3k+1] = ci+i [W3 ] + 42ci [W? ] + 66j W ] + 54bj_i [W3 ] + 30ci [W? ] + 27ci' [W? ]
ai_1 [W3k+1] = ci [W? ] + 42ci_1 [W3k ] + 6^1 [W? ] + 546i_2 [W? ] + 30cU W ]
+ 27ci_1[W3k ]
= ci[W3k ] + 42ci_1[W3k ] + 66j_1[W| ] + 54bi_2[W3k ] + 30a,_2[W3k ] + 27ci'_1 [W3k]	(by inductive hypothesis)
= c^1]
□
Remark 2.6. Corollary 2.7 below shows that the genus distribution sequence of an iterated 3-wheel is dominated by the genus distribution sequence of the successive member of the family of iterated 3-wheels. All iteratively defined graph families do not necessarily exhibit this characteristic. For instance, the edge-amalgamated open chains containing one, two and three copies of K3 3, respectively, have rising minimum genus [13].
Corollary 2.7. The genus distribution sequence of W? is dominated by the genus distribution sequence of W?+1
Proof. By re-arranging the terms, Equation (2.5) may be re-written as
«iWT1] = aiWi] + MW?] + ci[W3n] + ci'W?] + (42a,_1[W3n ] + 56; [W?] + 546i_1[W3n] + 29ci[W?] + 26ci'[W?]) = giW? ] + (42aj_1 [W?] + 56j [W?] + 546^1^] + 29^"] + 26ci'[W?])
It follows that gi[W3n+1] > gi[W3n], for all i > 0.	□
2.4 Genus distributions of W32, W33, W34, and W35
By using the Heffter-Edmonds face-tracing algorithm the partitioned genus distribution of
W? is
a0[W;1] = 2 b1[W31] = 12 ci[W;1] = 2
Substituting these values into the recurrences given in Corollary 2.4, we get the partitioned genus distribution of W32 as follows:
402
Ars Math. Contemp. 7 (2014) 379-432
aoW2
MW2
c0[W2
cO'IWl
ai[W3
bi[W32
c1[W32 c'i'[W32
a2 [W3 62 [W32
c2[w32
[W
a3[W32 63 [W2
c3 [w32 c3'[w2
= ao = 2 = 0 = 0 =0
= a1 + 42a0 + 661 + 54b0 + 30c1 + 27ci' = 0 + 42 x 2 + 6 x 12 + 0 + 30 x 2 + 0 = 216 = 15a0 + 15ci = 15 x 2+15 x 2 = 60
= ci =2 =0
= 5461 = 54 x 12 = 648
= 117a0 + 7261 + 117ci = 117 x 2 + 72 x 12 + 117 x 2 = = 30a0 + 661 + 42c1 = 30 x 2 + 6 x 12 + 42 x 2 = 216 = 11a0 + 11c1 = 11 x 2+11 x 2 = 44
=0 =0
= 5461 = 54 x 12 = 648 = 2461 = 24 x 12 = 288
1332
The partitioned genus distribution of W3 and the genus distribution obtained from it is listed in Table 2.1.
Table 2.1: Genus distribution of W32.
c
i	ai	bi	ci	ci'	di
0	2	0	0	0	2
1	216	60	2	0	278
2	648	1332	216	44	2240
3	0	0	648	288	936
For partitioned genus distribution of Wf, we again use Corollary 2.4 and substitute the values of partials of W3 from Table 2.1 as follows:
ao [W|] = ao = 2 bo [Wf] = 0 c0 [Wf] = 0 co [W|] = 0
M. I. Poshni et al.: Genus distributions of iterated 3-wheels and 3-prisms
433
ai[Wf 6i[Wf clW c'i'[Wf
a2 [Wg
62 [W33
c2[w| c2'[w|
a3 [W|
63 [W33
c3[W33
c3'[w|
a4[W| b4 [W33
c4[W33
a1 + 42a0 + 661 + 30c! = 216 + 42 x 2 + 6 x 60 + 30 x 2 = 720 15a0 + 15c1 = 15 x 2+15 x 2 = 60
c! = 2 0
a2 + 42a1 + 6b2 + 5461 + 30c2 + 27c2'
648 + 42 x 216 + 6 x 1332 + 54 x 60 + 30 x 216 + 27 x 44 = 28620 15a1 + 117a0 + 7261 + 15c2 + 117c!
15 x 216 + 117 x 2 + 72 x 60 + 15 x 216 + 117 x 2 = 11268 30a0 + 661 + c2 + 42c1 = 30 x 2 + 6 x 60 + 216 + 42 x 2 = 720 11a0 + 11c1 = 11 x 2+11 x 2 = 44
42a2 + 54b2 + 30c3 + 27c3'
42 x 648 + 54 x 1332 + 30 x 648 + 27 x 288 = 126360 15a2 + 117a1 + 72b2 + 15c3 + 117c2 + 162c2'
15 x 648 + 117 x 216 + 72 x 1332 + 15 x 648 + 117 x 216 + 162 x 44 173016
30a1 + 5461 + 6b2 + c3 + 42c2 + 27c2'
30 x 216 + 54 x 60 + 6 x 1332 + 648 + 42 x 216 + 27 x 44 = 28620 11a1 + 2461 + 11c2 = 11 x 216 + 24 x 60+ 11 x 216 = 6192
0
= 117a2 + 117c3 + 162c3' = 117 x 648 + 117 x 648 + 162 x 288 = 198288 = 30a2 + 54b2 + 42c3 + 27c^' = 30 x 648 + 54 x 1332 + 42 x 648 + 27 x 288 = 126360 c4'[W|] = 11a2 + 24b2 + 11c3 = 11 x 648 + 24 x 1332 + 11 x 648 = 46224 The partitioned genus distribution and the genus distribution of W3 is given in Table 2.2.
Table 2.2: Genus distribution of W33.
i	ai	bi	ci	ci	gi
0	2	0	0	0	2
1	720	60	2	0	782
2	28620	11268	720	44	40652
3	126360	173016	28620	6192	334188
4	0	198288	126360	46224	370872
Similar computations can be made for larger values of n. See Tables 2.3-2.4 for genus distributions of and W|.
402	Ars Math. Contemp. 7 (2014) 379-434
Table 2.3: Genus distribution of W3.
2
1224 152496 4000752 20878560 10707552 0
bi
0 60
26388 1845504 23948136 51333264 0
ci	c"	9i
0	0	2
2	0	1286
1224	44	180152
152496	17280	6016032
4000752	900072	49727520
20878560	6932304	89851680
10707552	4758912	15466464
Table 2.4: Genus distribution of Wf.
i	ai	bi	ci	c" i	9i
0	2	0	0	0	2
1	1728	60	2	0	1790
2	403380	41508	1728	44	446660
3	27945000	6768360	403380	28368	35145108
4	576580680	291382272	27945000	3988224	899896176
5	3302335008	3432610224	576580680	132308640	7443834552
6	3671430624	10025837856	3302335008	1034083584	18033687072
7	0	3276510912	3671430624	1467564480	8415506016
a
3 Genus distributions of iterated 3-prisms
Subdivision of any two edges incident on the root-vertex v of (W^-1, v), and adding an edge between the subdivision vertices produces the graph (Pr3, v). For the rest of this section, we use the term edge-addition to refer to this particular operation. Each embedding iw of (W3n-1, v) induces four embeddings of (PrJ,v) under edge-addition. The partial-types of the four embeddings of Pr3 produced are determined by the partial-type of the embedding iw.
3.1 Productions for edge-addition
Akin to productions for rim-insertion, one can also define productions for other graph operations. In what follows, we derive productions for the edge-addition operation:
Theorem 3.1. When an embedding of the single-rooted graph (W3-1, v) of partial-type a, c' or c" undergoes the edge-addition operation to produce (Pr3, v), the types of embeddings of Prn produced are specified by the following productions:
ai[W3n-1] ai[Prn]+3bi+i[Prn]	(3.1)
ciWT1] 3bi[Pr3n]+ ci[Pr3n]	(3.2)
ci'WT1] 4bi[Pr3n]	(3.3)
M. I. Poshni et al.: Genus distributions of iterated 3-wheels and 3-prisms
435
Proof. In any given embedding of W33-1 of type a, subdividing the edges incident on the root-vertex ensures that each pair of subdivision vertices occurs in exactly one of the fb-walks incident on the root-vertex. Because of this symmetry, for any choice of subdivision vertices adding an edge between them results in the same type of embeddings. As illustrated in Figure 3.1, the partial-types and genera of the embeddings produced as a result are specified by Production (3.1).
Figure 3.1: Production (3.1).
A similar argument can be made for the productions for types c' and c''. These are visualized in Figure 3.2 and Figure 3.3, respectively.	□
Figure 3.2: Production (3.2).
Figure 3.3: Production (3.3).
Theorem 3.2. When an embedding of the single-rooted graph (WJ-1, v) of partial-type b undergoes the edge-addition operation to produce (Pr^,v), the types of embeddings of Prn produced are specified by only one of the following two productions:
bi[Wn-1] 2ai[Pr3"]+2ci+i[Pr3"]	(3.4)
bi[W3n-1] a[Pr3n] + bi[Pr3n] + 2ci+i[Pr3n]	(3.5)
Proof. Let i be a type b embedding. The left-hand-side of Figure 3.4 illustrates how subdividing the three edges incident on the root-vertex produces the subdivision vertices v1,
436
ArsMath. Contemp. 7(2014)405-421
v2 and v3 such that the fb-walks incident on the root-vertex are (vi * v2 * v2 * v3*) and (v3 * v1 *), where * represents zero or more occurrences of vertices other than the subdivision vertices. Figure 3.4 illustrates the case when an edge-addition takes place between v1 and v2. By symmetry, this is also true for the case when an edge is added between v2 and v3. Both cases correspond to Production (3.4).
Figure 3.4: Production (3.4).
Production (3.5) specifies the scenario when an edge is added between vi and v3, as shown in Figure 3.5.	□
Figure 3.5: Production (3.5).
Corollary 3.3. Let ti represent an embedding of Pr" of genus i and any partial-type. When an embedding of the single-rooted graph (WJ-1,v) undergoes the edge-addition operation, the genera of the embeddings of Pr" produced are specified as follows:
ai [WJ-1]	ti[Pr3]+3ti+i[Pr3]	(3.6)
bi[WJ-1]	2ti[Pr3] + 2ti+1[Pr3]	(3.7)
ci [W33-1]	3ti [Pr"] + ti [Pr"]	(3.8)
ci'[W33-1]	4ti[Pr3]	(3.9)
Proof. Productions (3.6), (3.8) and (3.9) follow directly from Theorem 3.1. Production (3.7) follows from Theorem 3.2, as an embedding of WJ-1 of partial-type b and genus i in all cases produces two embeddings of Pr" of genus i and two of genus i + 1.	□
Corollary 3.4. Given the partitioned genus distribution of single-rooted graph (WJ-1, v), the genus distribution of the graph Pr" is specified by the following formula:
9i [Pr3 ] = ai[WJ-1] + 3ai-1[WJ-1] + 2bi[WJ-1] +	-1] (3.10)
+ 4ci [WJ-1] + 4ci'[WJ-1]
Proof. This follows by transposing the productions in Corollary 3.3.	□
Remark 3.5. It may be observed that the genus distribution sequence of Pr" also dominates the genus distribution sequence of WJ-1.
M. I. Poshni et al.: Genus distributions of iterated 3-wheels and 3-prisms
437
3.2 Genus distributions of small iterated 3-prisms
The genus distribution of Pr3 can be computed by substituting the values of the partitioned genus distribution of W^-1 into Equation (3.10), for n > 2. We show this for n = 3 and n = 4 by substituting values from Tables 2.1 and 2.2 into Equation (3.10) as follows:
Genus distribution of Pr§
go[Pr3] = aoW2] + 26o[W3] + 4c0[W| ] + 4c£ W] = 2 + 2 x 0 + 4 x 0 + 4 x 0 = 2
gi [Pr3] = ai [W32] + 3ao [W32] + 26i [W32 ] + 26o [W32] + 4c1 [W32] + 4c'/ [W32] = 216 + 3 x 2 + 2 x 60 + 2 x 0 + 4 x 2 + 4 x 0 = 350
g2 [Pr3] = a2 [W32] + 3ai [W32] + 262 [W32 ] + 26i [W32] + 4c2 [W32] + 4c2' [W32] = 648 + 3 x 216 + 2 x 1332 + 2 x 60 + 4 x 216 + 4 x 44 = 5120
g3 [Pr3] = a3 [W2] + 3a2 [W2] + 263 [W2 ] + 262 [W2] + 4c3 [W2] + 4c3' [W2] = 0 + 3 x 648 + 2 x 0 + 2 x 1332 + 4 x 648 + 4 x 288 = 8352
Genus distribution of Pr|
go [Pr|] = ao[W33 ] + 26o [W3] + 4co[W33] + 4co'[W33] = 2 + 2 x 0 + 4 x 0 + 4 x 0 = 2
gi [Pr|] = ai [W33 ] + 3ao [W33] + 26i [W33] + 26o [W33] + 4ci [W33] + 4ci' [W33] = 720 + 3 x 2 + 2 x 60 + 2 x 0 + 4 x 2 + 4 x 0 = 854
g2 [Pr|] = a2 [W33 ] + 3ai [W33] + 262 [W33] + 26i [W33] + 4c2 [W33] + 4c2'[W33]
= 28620 + 3 x 720 + 2 x 11268 + 2 x 60 + 4 x 720 + 4 x 44 = 56492
g3 [Pr|] = a3 [W33 ] + 3a2 [W33] + 263 [W33] + 262 [W33] + 4c3 [W33] + 4c3' [W33]
=	126360 + 3 x 28620 + 2 x 173016 + 2 x 11268 + 4 x 28620 + 4 x 6192
=	720036
g4 [Pr|] =	a4[Wf ] + 3a3[W33]+ 264[W33]+ 263[W33]+4c4[W33]+4c4'[W33]
=	0 + 3 x 126360 + 2 x 198288 + 2 x 173016 + 4 x 126360 + 4 x 46224
=	1812024
g5 [Pr4] =	a5 [W33 ] + 3a4 [W33] + 265 [W33] + 264 [W3] + 4c5 [W3] + 4c5' [W33]
=	0 + 3 x 0 + 2 x 0 + 2 x 198288 + 4 x 0 + 4 x 0 = 396576
In a similar manner, genus distributions of Pr3 can be computed for larger values of n. We show genus distributions of PrJ for some small values of n in Table 3.1
402	Ars Math. Contemp. 7 (2014) 379-438
Table 3.1: Genus distributions of Pr3, for n = 5,6, 7, and 8.
gi	Pr5	Pr6	Pr37	Pr8
go	2	2	2	2
g1	1358	1862	2366	2870
g2	214136	498788	910448	1449116
g3	8881128	44501868	137348784	319427892
g4	104071392	1384449840	8434131048	32260431816
g5	335149488	15315619320	215271967896	1516697746416
g6	196655040	57841006176	2282687116992	33465180312144
g7	0	58174969824	9638974212192	343447934792400
g8	0	0	13727729155968	1575240986550240
g9	0	0	4218604167168	2866735730052288
g10	0	0	0	1571115983393664
As noted in Remark 3.5, genus distribution of the iterated 3-prism PrJ always dominates genus distribution of the iterated 3-wheel W33-1, where Pr3 is obtained by adding an edge to a homeomorphic copy of W^-1. A shift in perspective would be to view the iterated 3-wheel as having been obtained from Pr3 by adding a 3-valent vertex to it. A natural question here would be to ask how the genus distributions of W<3 and PrJ compare. From Tables 2.1-2.4 and Table 3.1, it can be observed that genus distribution of Wn dominates the genus distribution of Pr3, for small values of n. In fact, this is true in general as the following theorem shows:
Theorem 3.6. Genus distribution of dominates the genus distribution of PrJ.
Proof. Let v1, v2, v3 be the three vertices in Pr3 to which a new vertex is joined, in order to obtain Wg\ There are 8 possible sets of rotations at these three vertices. For each such set of rotations, examining the strands of fb-walks incident at v1, v2, and v3 leads to the conclusion that every embedding of PrJ contains a face in which all three vertices appear. Thus, for every embedding of Pr3, it is possible to obtain an embedding of on the same surface, by placing the new vertex in that face. It follows that for each surface, there are at-least as many embeddings of as there are for Pr3.	□
4 Conclusions
Unlike previous results using the rooted-graphs method, this paper uses a single unchanging root-vertex for computing genus distributions for each member of the family of iterated 3-wheels and of the family of iterated 3-prisms Pr3. This paper also establishes that the sequence of genus distribution of W33 dominates the sequence of genus distribution of PrJ, which in turn dominates the sequence of genus distribution of W^-1.
A general direction for future work is to programatically examine the possibilities for manipulating root-vertices for computing genus distributions. The approach and algorithm used in this paper seem in principle to be extendible to Pr33, for any fixed m, with a cor-
M. I. Poshni et al.: Genus distributions of iterated 3-wheels and 3-prisms
439
responding increase in the size of the productions and partials, with definitions of partials based on integer partitions analogous to the way they have been defined in [8].
Some questions raised by this paper are as follows:
1.	In keeping with the strong unimodality conjecture, genus distributions of iterated 3-wheels Wip and 3-prisms Pr3, that were computed for small values of n, were found to be log concave. Can the recurrences for the partials be analyzed for affirming the log concavity of genus distributions for these families?
2.	It can also be observed from Tables 2.1-2.4 that for some small iterated 3-wheels the mode of the genus distribution is either the maximum genus or one less than the maximum genus. For larger n, the mode seems to migrate backwards. Our empirical evidence suggests that for large n, the ratio of the maximum genus of Wip to the mode of its genus distribution is approximately 1.185. Can this be proven using the recurrences for the partials of iterated 3-wheels?
3.	The distribution of each partial is observed to be log concave for the iterated 3-wheel Wip, for small values of n (See Tables 2.1-2.4 for n = 2, 3,4, and 5). Does this hold true in general?
4.	In case of W3n-i and Prp, it is clear that the domination of genus distribution of Pr3 is an outcome of the fact that it is obtained from Wip-1 by an edge-addition between vertices adjacent to the 3-valent root vertex of Wip-1. This means that for any embedding of Wip-1, there is a way to embed this edge in a way that subdivides a face. For the same reason, it is also clear that if we were to take an arbitrary graph G with a 3-valent vertex, then subdividing any two edges incident on the 3-valent vertex and adding an edge between the subdivision vertices, results in graph whose genus distribution dominates the genus distribution of G. The result does not generalize to graphs with edges that do not share a 3-valent endpoint. For instance, a dipole D4 has 6 planar embeddings, but subdividing two edges and adding an edge between the subdivision vertices produces a graph with 4 planar embeddings. Similarly, the result does not generalize to the case where the edges being subdivided do not share a common endpoint, for instance, it is possible to subdivide two edges of the planar circular ladder CL3 and add an edge between the subdivision vertices so as to produce a homeomorphic copy of K,3 in the resultant graph. It would be interesting to have general results that characterize the operations that, when applied to a graph, produce graphs whose genus distributions dominate that of the original graph.
References
[1]	J. Chen, J. L. Gross and R. G. Rieper, Overlap matrices and total imbedding distributions, Discrete Math. 128 (1994), 73-94.
[2]	Y. C. Chen, Y. P. Liu and T. Wang, The total embedding distributions of cacti and necklaces, Acta Math. Sinica — English Series 22 (2006), 1583-1590.
[3]	Y. Chen, T. Mansour and Q. Zou, Embedding distributions of generalized fan graphs, Acta Math. Sinica — English Series 22 (2006), 1583-1590. Canad. Math. Bull. (2011) Online 31, August.
402
Ars Math. Contemp. 7 (2014) 379-440
[4]	J. L. Gross, Genus distribution of graph amalgamations: Self-pasting atroot-vertices, Australas. J. Combin. 49 (2011), 19-38.
[5]	J. L. Gross and M. L. Furst, Hierarchy for imbedding-distribution invariants of a graph, J. Graph Theory 11 (1987), 205-220.
[6]	J. L. Gross, I. F. Khan and M. I. Poshni, Genus distribution of graph amalgamations: Pasting at root-vertices, Ars Combin. 94 (2010), 33-53.
[7]	J. L. Gross and T. W. Tucker, Topological Graph Theory, Dover, 2001; (original edn. Wiley, 1987).
[8]	I. F. Khan, M. I. Poshni and J. L. Gross, Genus distribution of graph amalgamations: Pasting when one root has arbitrary degree, Ars Math. Contemp. 3 (2010), 121-138.
[9]	J. H. Kwak and J. Lee, Genus polynomials of dipoles, KyungpookMath. J. 33 (1993), 115-125.
[10]	J. H. Kwak and J. Lee, Enumeration of graph embeddings, Discrete Math. 135 (1994), 129151.
[11]	J. H. Kwak and S. H. Shim, Total embedding distributions for bouquets of circles, Discrete Math. 248 (2002), 93-108.
[12]	B. P. Mull, Enumerating the orientable 2-cell imbeddings of complete bipartite graphs, J. Graph Theory 30 (1999), 77-90.
[13]	M. I. Poshni, I. F. Khan and J. L. Gross, Genus distributions of graphs under edge-amalgamations, Ars Math. Contemp. 3 (2010), 69-86.
[14]	M. I. Poshni, I. F. Khan and J. L. Gross, Genus distributions of graphs under self-edge-amalgamations, Ars Math. Contemp. 5 (2012), 127-148.
[15]	S. Stahl, Region distributions of graph embeddings and Stirling numbers, Discrete Math. 82 (1990), 57-78.
[16]	S. Stahl, Permutation-partition pairs III: Embedding distributions of linear families of graphs, J. Combin. Theory (B) 52 (1991), 191-218.
[17]	S. Stahl, On the zeroes of some genus polynomials, Canad. J. Math. 49 (1997), 617-640.
[18]	E. H. Tesar, Genus distribution of Ringel ladders, Discrete Math. 216 (2000) 235-252.
[19]	T. I. Visentin and S. W. Wieler, On the genus distribution of (p, q,n)-dipoles, Electronic J. Combin. 14 (2007), Art. No. R12.
[20]	L. X. Wan and Y. P. Liu, Orientable embedding distributions by genus for certain types of graphs, Ars Combin. 79 (2006), 97-105.
[21]	L. X. Wan and Y. P. Liu, Orientable embedding genus distribution for certain types of graphs, J. Combin. Theory (B) 47 (2008), 19-32.
[22]	A. T. White, Graphs of Groups on Surfaces, North-Holland, 2001.