Also available at http://amc.imfm.si
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 5 (2012) 127–148
Genus distributions of graphs under
self-edge-amalgamations
Mehvish I. Poshni , Imran F. Khan , Jonathan L. Gross
Columbia University, Department of Computer Science NY 10027 USA, New York, USA
Received 19 July 2010, accepted 29 July 2011, published online 12 January 2012
Abstract
We investigate the well-known problem of counting graph imbeddings on all oriented
surfaces with a focus on graphs that are obtained by pasting together two root-edges of
another base graph. We require that the partitioned genus distribution of the base graph
with respect to these root-edges be known and that both root-edges have two 2-valent end-
points. We derive general formulas for calculating the genus distributions of graphs that can
be obtained either by self-co-amalgamating or by self-contra-amalgamating a base graph
whose partitioned genus distribution is already known. We see how these general formulas
provide a unified approach to calculating genus distributions of many new graph families,
such as co-pasted and contra-pasted closed chains of copies of the triangular prism graph,
as well as graph families like circular and Möbius ladders with previously known solutions
to the genus distribution problem.
Keywords: Graph, genus distribution, self-edge-amalgamation.
Math. Subj. Class.: 05C10
1 Introduction
Prior research on the problem of counting oriented imbeddings of graphs on all 2-manifolds
has yielded closed formulas, recursions for generating tabular data, and asymptotic lower
bounds for various families of graphs. Our first installment [22] demonstrated a method
for calculating partitioned genus distributions of arbitrarily long edge-linked chains ob-
tained by iteratively edge-amalgamating copies of one or more base graphs of known par-
titioned genus distribution. In this installment, we develop two formulas that use the parti-
tioned genus distribution of a graph to calculate the genus distribution of the graph obtained
through self-edge-amalgamation of its two roots. Thus, combined with the results derived
E-mail addresses: poshni@cs.columbia.edu (Mehvish I. Poshni), imran@cs.columbia.edu (Imran F. Khan),
gross@cs.columbia.edu (Jonathan L. Gross)
Copyright c© 2012 DMFA Slovenije
128 Ars Math. Contemp. 5 (2012) 127–148
in the first installment, we can first obtain a recursion for the genus distributions of an in-
finite family of open chains of edge-amalgamated copies of a base graph, and then apply
the two formulas derived in this paper to obtain genus distributions of the corresponding
one or two infinite families of closed chains. In this manner, one can calculate the genus
distribution for arbitrarily large graphs. This paper is self-contained, though we strongly
recommend reading [22] before reading this paper.
Precedents for work on counting imbeddings on various orientable and non-orientable
surfaces include [2], [3], [4], [10], [12], [16], [17], [18], [20], [21], [24], [25], [26], [27],
[28], [29], and [30] amongst many others. Some recent endeavors in this context have
resulted in a series of related works in [11], [14], [7], [8], [9] and [23]. Prior work on
counting graph imbeddings in a minimum-genus surface includes [1], [5], [6], and [15].
We briefly review some of the terminology introduced in [22].
We define a double-edge-rooted graph as a graph that has two distinct edges designated
as root-edges, or more simply, as roots. In this paper, we require that a root-edge have two
2-valent endpoints. We use the notation (G, e, f) to mean that G is double-edge-rooted,
with edges e and f serving as root-edges. We can abbreviate (G, e, f) as G where it is
clear from context that a double-edge-rooted graph is intended. A closed walk traced just
inside the boundary of a face of an embedding is referred to as a face-boundary walk. We
abbreviate face-boundary walk as fb-walk. We define a strand, with respect to a root-edge
e (e-strand for short), to be an open subwalk of an fb-walk that runs between any two
occurrences of the endpoints of e, such that it has in its interior neither an occurrence of e
nor of the endpoints of e.
The remainder of this section reviews some concepts and terminology introduced in the
first installment of this paper, followed by a formal description of the self-edge-amalgama-
tion operation.
First-order sub-partials
For each imbedding of a double-edge-rooted graph, there are two possibilities for each of
its root-edges. Either,
• two distinct fb-walks are incident on it;
• or the same fb-walk is incident on both sides of it.
Accordingly, we use the mnemonic d for “different” and s for “same”, and we categorize
each imbedding of the double-edge-rooted graph (G, e, f) into the four types: dd, ds, sd,
or ss. The first letter in each of these types is for root-edge e and the second for the root-
edge f .
The genus distribution of a double-edge-rooted graph (G, e, f) is further partitioned
into the double-root partials ddi(G, e, f), dsi(G, e, f), sdi(G, e, f), ssi(G, e, f). These
are the numbers of cellular imbeddings of (G, e, f) on the surface Si having types dd, ds,
sd, or ss, respectively. For the purpose of our derivations, these partials are refined into the
following first-order sub-partials:
• dd0i (G, e, f), ds0i (G, e, f), sd0i (G, e, f) and ss0i (G, e, f) are the numbers of imbed-
dings of G on surface Si of types dd, ds, sd and ss, respectively, such that none of
the fb-walks incident on e is incident on f .
• dd′i(G, e, f), ds′i(G, e, f), and sd′i(G, e, f) are the numbers of imbeddings of G on
surface Si of types dd, ds and sd, respectively, such that exactly one fb-walk incident
on e is also incident on f .
M. I. Poshni, I. F. Khan and J. L. Gross: Genus distributions of graphs. . . 129
• dd′′i (G, e, f) is the number of imbeddings of G on surface Si of type dd such that
both fb-walks incident on e are also incident on f .
• ss1i (G, e, f) and ss2i (G, e, f) partition the number of imbeddings on surface Si of
type ss which are not of sub-type ss0. The sub-partial ss1 counts the cases where
exactly one e-strand contains both occurrences of f , while the sub-partial ss2 counts
the cases where each e-strand contains an occurrence of f .
It follows from these definitions that each double-root partial is the sum of its first-order
sub-partials. Moreover,
gi(G) = ddi(G) + dsi(G) + sdi(G) + ssi(G)
Second-order sub-partials
The four first-order sub-partials dd′, dd′′, ds′ and sd′ are further refined into second-order
sub-partials. To define these, we imagine assigning arbitrary orientations to root-edges
e and f of the graph (G, e, f). These assigned orientations are referred to as pasting-
orientations of root-edges. Given an oriented imbedding of (G, e, f), as we walk along
the oriented root-edge e towards its head, the left side of the edge is labeled 1 and the right
side is labeled 2. Whereas when we walk along root-edge f towards its head, the left side
is labeled 3 and the right side is labeled 4. This is illustrated in Figure 1.
1 2 3 4
e f
Figure 1: Model for second-order sub-partials with labelled edge-sides.
Accordingly, the second-order partials are described as follows:
• By definition, a dd′-type imbedding has exactly one fb-walk incident on both root-
edges. However, the fb-walk incident on both root-edges may combine either the
faces 1 and 4, the faces 2 and 3, the faces 1 and 3, or the faces 2 and 4. Accordingly,
we define dd′i(G, e, f), d̃d′i(G, e, f),
−→
dd′i(G, e, f) and
←−
dd′i(G, e, f) to be the num-
bers of imbeddings of type dd′i such that (1,4), (2,3), (1,3) and (2,4) are the respective
pairs of sides that occur on the same fb-walk, as shown in the top row of Figure 2.
•
−→
dd′′i(G, e, f) is the number of imbeddings of type dd′′i such that the pair of sides
(1,4) occurs on one of the fb-walks incident on the root-edges e and f and the pair
of sides (2,3) occurs on the other. Also,
←−
dd′′i(G, e, f) is defined similarly, but with
(1,3) and (2,4) as pairs of sides occurring on the two fb-walks incident on root-edges
e and f .
•
−→
ds′i(G, e, f) and
←−
ds′i(G, e, f) are the numbers of imbeddings of type ds′ such that
the three sides 1,3,4 (in the former case) and the three sides 2,3,4 (in the latter case)
all occur on the same fb-walk.
•
−→
sd′i(G, e, f) and
←−
sd′i(G, e, f) are the numbers of imbeddings of type sd′ such that
the three sides 1,2,4 (in the former case) and the three sides 1,2,3 (in the latter case)
all occur in the same fb-walk.
130 Ars Math. Contemp. 5 (2012) 127–148
Clearly, each first-order sub-partial is the sum of its second-order sub-partials. A par-
titioned genus distribution of a graph is its genus distribution partitioned into sub-partials.
Figure 2: Modeling second-order sub-partials.
Self-edge-amalgamation
The self-edge-amalgamation of a graph is an operation whereby two root-edges of a
double-edge-rooted graph are pasted together. Amongst many other classes, one can ob-
tain families of closed chains of graphs, including circular ladders and Möbius ladders,
by applying self-edge-amalgamation to families of open chains, such as the closed-end
ladders. Informally, we use pasting to refer to any kind of amalgamation. Where it is
clear from context that a self-edge-amalgamation is intended, we may use the terminology
self-amalgamation. We denote this operation by a monadic operator acting on a double-
edge-rooted graph operand (G, e, f):
W = ∗ef (G, e, f)
The self-edge-amalgamation of a double-edge-rooted graph (G, e, f) produces a graph
W obtained from G by identifying edges e and f . We fix the pasting-orientations on the
root-edges by arbitrarily orienting e and f . Accordingly, the edge-ends of e and f at the
tail are e− and f−, while the ones at the head are e+ and f+. Now edges e and f can be
pasted in two different ways. One way of pasting, called co-self-amalgamation, identifies
the edge-end e− with f− and the edge-end e+ with f+. The other way of pasting, called
contra-self-amalgamation, pairs the edge-end e− with f+ and the edge-end e+ with f−.
These two ways of self-edge-amalgamating a graph produces graphs which may be non-
isomorphic, as seen later in this paper.
REMARK Assignment of labels 1 through 4 to the edge-sides of root-edges is also relative
to these same pasting-orientations.
M. I. Poshni, I. F. Khan and J. L. Gross: Genus distributions of graphs. . . 131
We defined open chains in [22] as graphs formed by iteratively pasting copies of
smaller graphs along root-edges. Graphs that are obtained from a self-amalgamation of
double-edge-rooted open chains are referred to as closed chains. Depending on which type
of pasting is used, these may be classified as co-pasted or contra-pasted closed chains.
We work under the assumption that we already have the partitioned genus distribution
of the graph that we wish to self-edge-amalgamate. For smaller graphs, this can be done
easily by using the Heffter-Edmonds algorithm [13]. For large graphs, some new ways of
finding partitioned genus distributions are presented in [11], [14] and [22].
2 Productions for self-edge-amalgamation
Let xi be any double-root sub-partial. Then a production is used to represent the ways
in which an imbedding of a double-edge-rooted graph (G, e, f) of type x on surface Si
self-edge-amalgamates on the root-edges e and f to give various types of imbeddings of
the resulting graph W . Formally, we write
xi(G, e, f) −→ gk1(W ) + gk2(W ) + gk3(W ) + gk4(W )
where k1, k2, k3, k4 are (not necessarily distinct) integer-valued functions of i. This can be
read as follows:
An imbedding of (G, e, f) of type x on surface Si self-amalgamates on the
root-edges e and f to give four imbeddings of the graph W on the surfaces
Sk1 , Sk2 , Sk3 and Sk4 .
The left-hand side of the production is known as the production head and the right-hand
side of the production as the production body.
REMARK The number of terms in the production body could be larger if the degrees of the
endpoints of root-edges were larger.
The production, as we have defined it, does not specify whether the self-amalgamation
is a co-self-paste or a contra-self-paste. However, as we shall see, for an application that
seeks to find the genus distribution of a self-amalgamated graph, the system of productions
will consistently refer to only one of the two types of self-pasting. While considering the
self-edge-amalgamation for an imbedding on an oriented surface and modeling it using a
production, it is important to maintain a sense of orientation of the strands. Each imbedding
of a self-edge-amalgamated graph W = ∗ef (G, e, f) induces a unique imbedding of the
graph G, such that the rotation system of W is consistent with the rotation system of G.
Theorem 2.1. Let (G, e, f) be a double-edge-rooted graph, where both root-edges have
two 2-valent endpoints. Then the following productions apply to all scenarios of co-self-
paste and contra-self-paste in which no fb-walk of the imbedding of G is incident on both
root-edges e and f :
dd0i (G) −→ 2gi+1(W ) + 2gi+2(W ) (2.1)
ds0i (G) −→ 4gi+1(W ) (2.2)
sd0i (G) −→ 4gi+1(W ) (2.3)
ss0i (G) −→ 4gi+1(W ) (2.4)
132 Ars Math. Contemp. 5 (2012) 127–148
Proof. The proof of Production (2.1) follows by face-tracing of the fb-walks incident on
both root-edges of the graph G. We examine in closer detail the recombination of strands
caused by a self-edge-amalgamation where the imbedding of graph G is of type dd0. The
production shown in the upper half of Figure 3 depicts the case of a co-self-paste while the
drawing in the lower half shows a contra-self-paste on the same root-edges. In both cases
we get the same results.
Figure 3: Productions for co-self-pasting and contra-self-pasting a dd0-type imbedding of
(G, e, f).
The self-amalgamation produces two fewer vertices and one less edge in each of the
four resultant graph imbeddings. The first and last imbeddings shown for each production
have two fb-walks merging as a consequence of self-amalgamation. In the second and third
imbeddings, all four fb-walks that are incident on the two root-edges merge into a single fb-
walk. Applying the Euler polyhedral equation, we see that in the former case the decrease
of a single face results in a genus increment of 1, while in the latter case the decrease of
three fb-walks results in a genus increment of 2. The proofs for the remaining productions
are similar and also follow by face-tracing. For the sake of brevity, we leave these to the
reader.
For imbeddings in which one or two fb-walks are incident on both root-edges, the
productions for co-self-pasting and contra-self-pasting may differ. In particular, for dd′
and dd′′ we get different results for both ways of pasting.
Theorem 2.2. Let (G, e, f) be a double-edge-rooted graph, where both root-edges have
two 2-valent endpoints. Then the following productions describe all cases of co-self-pasting
for imbeddings of G of type dd′:
dd′i(G) −→ gi(W ) + 3gi+1(W ) (2.5)
d̃d′i(G) −→ gi(W ) + 3gi+1(W ) (2.6)
M. I. Poshni, I. F. Khan and J. L. Gross: Genus distributions of graphs. . . 133
−→
dd′i(G) −→ 4gi+1(W ) (2.7)
←−
dd′i(G) −→ 4gi+1(W ) (2.8)
Furthermore, the following productions describe all cases of co-self-pasting for imbeddings
of G of type dd′′:
−→
dd′′i(G) −→ 4gi(W ) (2.9)
←−
dd′′i(G) −→ 2gi(W ) + 2gi+1(W ) (2.10)
Proof. For illustration of Production (2.5), which describes the effects of co-self-pasting a
dd′-type imbedding of G, we refer to the upper half of Figure 4. We observe that the first
imbedding of graph W stands out from the other three, in that there is a net increase of
one fb-walk as the fb-walk incident on both roots of the imbedding of G breaks into two
fb-walks during self-pasting. This does not occur in the other three cases, where there is a
net decrease of one fb-walk in the resulting imbedding. The former results in an unchanged
genus of the resultant graph imbedding, while the latter results in a genus increment of one.
This accounts for Production (2.5).
Figure 4: Productions for co-self-pasting dd′-type and
−→
dd′-type imbeddings of (G, e, f).
For Production (2.7), the illustration in the bottom half of Figure 4 shows that all four
imbeddings resulting from the self-pasting of G end up with one less face, thereby war-
ranting a genus increment of 1 for the resulting imbeddings. Proofs for Productions (2.6)
and (2.8) are similar to the proofs for (2.5) and (2.7), respectively, and we leave them to the
reader.
Productions (2.9) and (2.10) for co-self-pasting a
−→
dd′′- or a
←−
dd′′-type imbedding of G
can also be derived by using the same technique. We include Figure 5 for aiding the reader
with the proof of Production (2.10), and omit the proof of Production (2.9).
134 Ars Math. Contemp. 5 (2012) 127–148
Figure 5: Production for co-self-pasting a
←−
dd′′-type imbedding of (G, e, f).
Theorem 2.3. Let (G, e, f) be a double-edge-rooted graph, where both root-edges have
two 2-valent endpoints. Then the following productions apply for contra-self-pasting all
dd′-type imbeddings of G:
dd′i(G) −→ 4gi+1(W ) (2.11)
d̃d′i(G) −→ 4gi+1(W ) (2.12)
−→
dd′i(G) −→ gi(W ) + 3gi+1(W ) (2.13)
←−
dd′i(G) −→ gi(W ) + 3gi+1(W ) (2.14)
Furthermore, the following productions apply for contra-self-pasting all dd′′-type imbed-
dings of G:
−→
dd′′i(G) −→ 2gi(W ) + 2gi+1(W ) (2.15)
←−
dd′′i(G) −→ 4gi(W ) (2.16)
Proof. Figure 6 illustrates Production (2.12) in the upper half and Production (2.14) in the
bottom half.
For Production (2.12), in all four imbeddings resulting from the contra-self-pasting, the
three fb-walks incident on the root-edges of the graph G break into strands that merge into
two fb-walks, as shown in Figure 6. While, for Production (2.14), this happens for only
three of the resulting imbeddings of graph W . For the remaining imbedding, the fb-walks
break into strands that recombine to give four distinct fb-walks. Proofs of Productions
(2.11) and (2.13) are similar and left to the reader.
Similarly, applying contra-self-pasting to the root-edges of a
−→
dd′′-type imbedding of
(G, e, f) results in two imbeddings of W where all the fb-walks incident on the roots merge
into a single fb-walk, and two imbeddings where they break into strands that recombine
into three distinct fb-walks, as shown in Figure 7. This proves Production (2.15). Proof for
Production (2.16) is similar and we leave it to the reader.
M. I. Poshni, I. F. Khan and J. L. Gross: Genus distributions of graphs. . . 135
Figure 6: Productions for contra-self-pasting d̃d′-type and
←−
dd′-type imbeddings of
(G, e, f).
Figure 7: Production for contra-self-pasting
−→
dd′′-type imbeddings of (G, e, f).
Theorem 2.4. Let (G, e, f) be a double-edge-rooted graph, where both roots have two
2-valent endpoints. Then the following productions cover all scenarios for co-self-pasting
and contra-self-pasting, where the imbedding of G is of type ds′ or sd′:
ds′i(G) −→ 2gi(W ) + 2gi+1(W ) (2.17)
sd′i(G) −→ 2gi(W ) + 2gi+1(W ) (2.18)
Proof. Due to the symmetry of the models
−→
ds′ and
−→
sd′, and of
←−
ds′ and
←−
sd′, we need only
provide the proof for one of the two Productions (2.17) and (2.18). Figure 8 illustrates
the proof for the co-self-pasted and contra-self-pasted
−→
ds′-type imbedding of G. We get
two imbeddings with a genus increment of 0 and two with a genus increment of 1. We
leave the proof for a
←−
ds′-type imbedding of G to the reader. The reader will observe that
the production body for the imbedding type
←−
ds′ is identical to the production body for the
imbedding type
−→
ds′. This is true for both co-self-pasting and contra-self-pasting operations.
This completes the proof of Production (2.17).
136 Ars Math. Contemp. 5 (2012) 127–148
Figure 8: Productions for co-pasting and contra-pasting a
−→
ds′-type imbedding of (G, e, d).
Theorem 2.5. Let (G, e, f) be a double-edge-rooted graph, where both roots have two
2-valent endpoints. Then the following productions apply for co-self-pasting or contra-
self-pasting an ss1 or ss2-type imbedding of G:
ss1i (G) −→ 4gi(W ) (2.19)
ss2i (G) −→ 3gi(W ) + gi−1(W ) (2.20)
Proof. When the imbedding of a double-edge-rooted graph G is of type ss1, a self-amalga-
mation on the root-edges breaks the single fb-walk incident on both roots into strands that
recombine to give two fb-walks in all the corresponding imbeddings of the self-amalgama-
ted graph W . The additional face balances out the decrease of two vertices and one edge
to retain the same genus in each of the four resulting imbeddings of W . This holds for
co-self-pasting as well as contra-self-pasting as evident from Figure 9.
We leave the proof of Production 2.20 for the self-amalgamation of an ss2-type imbed-
ding to the reader.
REMARK As it turns out, the productions for second-order sub-partial types of dd′ and dd′′
are the only ones that disagree for a co-self-paste and a contra-self-paste. Moreover, the
results for the co- and contra-self-amalgamation for both dd′- and dd′′-type imbeddings
are symmetric in the sense that the production body for co-self-pasting a
−→
dd′′-type (or
a
←−
dd′′-type) imbedding of G is the same as the production body for contra-self-pasting
←−
dd′′-type (or a
−→
dd′′-type) imbedding of G. Likewise, for the pairs of dd′-, d̃d′-types of
imbeddings of G which show a symmetry with the
−→
dd′- ,
←−
dd′-types of imbeddings of G.
M. I. Poshni, I. F. Khan and J. L. Gross: Genus distributions of graphs. . . 137
Figure 9: Productions for co-self-pasting and contra-self-pasting an ss1-type imbedding of
(G, e, f).
Theorem 2.6. Let W be the graph formed by co-self-pasting of (G, e, f). Then,
gi(W ) = 2dd
0
i−2(G) + 2dd
0
i−1(G) + 3dd
′
i−1(G) + 3d̃d′i−1(G) + 4
−→
dd′i−1(G)
+ 4
←−
dd′i−1(G) + 2
←−
dd′′i−1(G) + 4ds
0
i−1(G) + 2ds
′
i−1(G) + 4sd
0
i−1(G)
+ 2sd′i−1(G) + 4ss
0
i−1(G) + dd
′
i(G) + d̃d′i(G) + 4
−→
dd′′i(G) + 2
←−
dd′′i(G)
+ 2ds′i(G) + 2sd
′
i(G) + 4ss
1
i (G) + 3ss
2
i (G) + ss
2
i+1(G) (2.21)
Proof. The Production (2.1):
dd0i (G) −→ 2gi+1(W ) + 2gi+2(W )
indicates that each dd0-type imbedding of (G, e, f) on the surface Si when self-amalga-
mated, induces two imbeddings of W on Si+1 and two on the surface Si+2. These con-
tributions account for the first two terms 2dd0i−2(G) + 2dd
0
i−1(G) on the right-hand side
of Equation (2.21). Taking into account all the contributions made by productions listed in
Theorems 2.1–2.5, the result follows.
Theorem 2.7. Let W be the graph formed by contra-self-pasting of (G, e, f). Then,
gi(W ) = 2dd
0
i−2(G) + 2dd
0
i−1(G) + 3
−→
dd′i−1(G) + 3
←−
dd′i−1(G) + 4dd′i−1(G)
+ 4d̃d′i−1(G) + 2
−→
dd′′i−1(G) + 4ds
0
i−1(G) + 2ds
′
i−1(G) + 4sd
0
i−1(G)
+ 2sd′i−1(G) + 4ss
0
i−1(G) +
−→
dd′i(G) +
←−
dd′i(G) + 4
←−
dd′′i(G) + 2
−→
dd′′i(G)
+ 2ds′i(G) + 2sd
′
i(G) + 4ss
1
i (G) + 3ss
2
i (G) + ss
2
i+1(G) (2.22)
Proof. The proof for Equation (2.22) is obvious from Equation (2.21) and our earlier
remarks on the symmetries of the productions for dd′ and dd′′ second-order sub-partial
types.
138 Ars Math. Contemp. 5 (2012) 127–148
Thus, depending on whether one plans on forming a closed chain through a co-self-
amalgamation or through a contra-self-amalgamation, the genus distribution of the closed
chain is calculated by using Theorems 2.6 or 2.7, respectively. For instance, using the
partitioned genus distributions calculated for closed-end ladders in [22], we can now use
Theorems 2.6 and 2.7 to obtain partitioned genus-distribution for both circular and Möbius
ladders.
3 Application: Revisiting circular ladders and Möbius ladders
The genus distributions of circular ladders and Möbius ladders were first derived by [19].
§4 of [22] shows how calculation of the double-root genus distributions of closed-end lad-
ders is reducible to a routine recursion. This in turn reduces the derivation of the genus
distributions of circular and Möbius ladders, in turn, to a routine substitution into an equa-
tion.
Let Ln be the closed-end ladder with 2 end-rungs and n interior rungs, as shown in
Figure 10.
Figure 10: Closed-end ladders Ln.
Let CLn denote the circular ladder with n rungs as illustrated in Figure 11. We observe
that co-self-pasting the closed-end ladder Ln on the root-edges yields CLn+1. Similarly,
Figure 11: Circular ladders CLn.
we denote a Möbius ladder with n rungs by MLn as shown in Figure 12. It can be observed
that contra-self-pasting the closed-end ladder Ln on the root-edges yields MLn+1 .
Figure 12: Möbius ladders MLn.
M. I. Poshni, I. F. Khan and J. L. Gross: Genus distributions of graphs. . . 139
We give a small example that demonstrates how to calculate genus distributions of
CL4 and ML4 from the partitioned genus distribution of L3. We begin by reproducing
in Table 1 the partitioned genus distribution of the closed-end ladder L3 originally derived
in [22].
Table 1: Double-root partials of L3.
L3
k 0 1 2 k 0 1 2
dd0k 6 0 0
−→
ds′k 0 2 0
dd′k 1 6 0
←−
ds′k 0 2 0
d̃d′k 1 6 0 sd
0
k 0 4 0
−→
dd′k 0 6 0
−→
sd′k 0 2 0
←−
dd′k 0 6 0
←−
sd′k 0 2 0
−→
dd′′k 0 0 0 ss
0
k 0 0 0
←−
dd′′k 0 0 0 ss
1
k 0 0 8
ds0k 0 4 0 ss
2
k 0 0 8
Simply plugging the values from Table 1 into Equation (2.21) yields the genus distributions
of circular ladder CL4.
g0(CL4) = dd′0(L3) + d̃d′0(L3) = 1 + 1 = 2
g1(CL4) = 2dd
0
0(L3) + 3dd
′
0(L3) + 3d̃d′0(L3) + dd′1(L3) + d̃d′1(L3) + 2ds
′
1(L3)
+ 2sd′1(L3) + ss
2
2(L3)
= 2× 6 + 3× 1 + 3× 1 + 6 + 6 + 2× 4 + 2× 4 + 8
= 54
g2(CL4) = 2dd
0
0(L3) + 3dd
′
1(L3) + 3d̃d′1(L3) + 4
−→
dd′1(L3) + 4
←−
dd′1(L3) + 4ds
0
1(L3)
+ 2ds′1(L3) + 4sd
0
1(L3) + 2sd
′
1(L3) + 4ss
1
2(L3) + 3ss
2
2(L3)
= 2× 6 + 3× 6 + 3× 6 + 4× 6 + 4× 6 + 4× 4 + 2× 4 + 4× 4
+ 2× 4 + 4× 8 + 3× 8
= 200
g3(CL4) = 0
140 Ars Math. Contemp. 5 (2012) 127–148
Whereas, plugging the values from Table 1 into Equation (2.22) produces the genus distri-
bution of the Möbius ladder ML4:
g0(ML4) = 0
g1(ML4) = 2dd
0
0(L3) + 4dd
′
0(L3) + 4d̃d′0(L3) +
−→
dd′1(L3) +
←−
dd′1(L3) + 2ds
′
1(L3)
+ 2sd′1(L3) + ss
2
2(L3)
= 2× 6 + 4× 1 + 4× 1 + 6 + 6 + 2× 4 + 2× 4 + 8
= 56
g2(ML4) = 2dd
0
0(L3) + 3
−→
dd′1(L3) + 3
←−
dd′1(L3) + 4dd′1(L3) + 4d̃d′1(L3)
+ 4ds01(L3) + 2ds
′
1(L3) + 4sd
0
1(L3) + 2sd
′
1(L3) + 4ss
1
2(L3) + 3ss
2
2(L3)
= 2× 6 + 3× 6 + 3× 6 + 4× 6 + 4× 6 + 4× 4 + 2× 4 + 4× 4 + 2× 4
+ 4× 8 + 3× 8
= 200
g3(ML4) = 0
4 Application: Closed chains of copies of a triangular prism graph
As an example of two entirely new calculations of genus distributions of closed chains, we
consider closed chains of copies of the triangular prism graph. Figure 13 shows a triangular
prism graph at the left, where two of its edges are trisected and their middle-thirds are
designated as root-edges. We show the root-edges darker by convention.
Let ∆G denote the double-edge-rooted triangular prism graph. Figure 13 shows some
small double-edge-rooted open chains of copies of the graph ∆G. We denote an open chain
consisting of n copies of ∆G by Prn.
Figure 13: Open chains of copies of a triangular prism graph.
We begin the derivations for closed chains of copies of ∆G by first producing the par-
titioned genus distribution of the open chains Pr1 and Pr2 in Table 2. These have been
derived using the methods in [22] .
M. I. Poshni, I. F. Khan and J. L. Gross: Genus distributions of graphs. . . 141
Table 2: Genus distributions of the open chains Pr1 and Pr2 of 1 and 2 copies of ∆G,
respectively.
Prn Pr1 Pr2
k 0 1 2 0 1 2 3 4
dd0k 0 0 0 6 176 704 0 0
dd′k 1 0 0 1 46 400 0 0
d̃d′k 1 0 0 1 46 400 0 0
−→
dd′k 0 0 0 0 22 256 0 0
←−
dd′k 0 0 0 0 22 256 0 0
−→
dd′′k 0 12 0 0 0 48 0 0
←−
dd′′k 0 0 0 0 0 48 0 0
ds0k 0 4 0 0 44 800 384 0
−→
ds′k 0 4 0 0 6 272 960 0
←−
ds′k 0 4 0 0 6 272 960 0
sd0k 0 4 0 0 44 800 384 0
−→
sd′k 0 4 0 0 6 272 960 0
←−
sd′k 0 4 0 0 6 272 960 0
ss0k 0 0 0 0 0 320 1888 0
ss1k 0 0 24 0 0 72 1664 2304
ss2k 0 2 0 0 0 8 288 0
gk 2 38 24 8 424 5200 8448 2304
Let CPrn be the co-self-amalgamated closed chain of n copies of ∆G, as shown in
Figure 14. We plug the values from Table 2 into Equation (2.21) to calculate genus distri-
butions for CPr1 and CPr2.
Figure 14: Co-pasted closed chains of copies of a triangular prism graph.
142 Ars Math. Contemp. 5 (2012) 127–148
We illustrate this as follows:
g0(CPr1) = dd′0(Pr1) + d̃d′0(Pr1) + 4
−→
dd′′0(Pr1) + 2
←−
dd′′0(Pr1) + 2ds′0(Pr1)
+ 2sd′0(Pr1) + 4ss10(Pr1) + 3ss20(Pr1) + ss21(Pr1)
= 1 + 1 + 4× 0 + 2× 0 + 2× 0 + 2× 0 + 4× 0 + 3× 0 + 2
= 4
g1(CPr1) = 2dd00(Pr1) + 3dd′0(Pr1) + 3d̃d′0(Pr1) + 4
−→
dd′0(Pr1) + 4
←−
dd′0(Pr1)
+ 2
←−
dd′′0(Pr1) + 4ds00(Pr1) + 2ds′0(Pr1) + 4sd00(Pr1) + 2sd′0(Pr1)
+ 4ss00(Pr1) + dd′1(Pr1) + d̃d′1(Pr1) + 4
−→
dd′′1(Pr1) + 2
←−
dd′′1(Pr1)
+ 2ds′1(Pr1) + 2sd′1(Pr1) + 4ss11(Pr1) + 3ss21(Pr1) + ss22(Pr1)
= 2× 0 + 3× 1 + 3× 1 + 4× 0 + 4× 0 + 2× 0 + 4× 0 + 2× 0
+ 4× 0 + 2× 0 + 4× 0 + 0 + 0 + 4× 12 + 2× 0 + 2× 8 + 2× 8
+ 4× 0 + 3× 2 + 0
= 92
g2(CPr1) = 2dd00(Pr1) + 2dd01(Pr1) + 3dd′1(Pr1) + 3d̃d′1(Pr1) + 4
−→
dd′1(Pr1)
+ 4
←−
dd′1(Pr1) + 2
←−
dd′′1(Pr1) + 4ds01(Pr1) + 2ds′1(Pr1) + 4sd01(Pr1)
+ 2sd′1(Pr1) + 4ss01(Pr1) + dd′2(Pr1) + d̃d′2(Pr1) + 4
−→
dd′′2(Pr1)
+ 2
←−
dd′′2(Pr1) + 2ds′2(Pr1) + 2sd′2(Pr1) + 4ss12(Pr1) + 3ss22(Pr1)
+ ss23(Pr1)
= 2× 0 + 2× 0 + 3× 0 + 3× 0 + 4× 0 + 4× 0 + 2× 0 + 4× 4 + 2× 8
+ 4× 4 + 2× 8 + 4× 0 + 0 + 0 + 4× 0 + 2× 0 + 2× 0 + 2× 0
+ 4× 24 + 3× 0 + 0
= 160
g0(CPr2) = dd′0(Pr2) + d̃d′0(Pr2) + 4
−→
dd′′0(Pr2) + 2
←−
dd′′0(Pr2) + 2ds′0(Pr2)
+ 2sd′0(Pr2) + 4ss10(Pr2) + 3ss20(Pr2) + ss21(Pr2)
= 1 + 1 + 4× 0 + 2× 0 + 2× 0 + 2× 0 + 4× 0 + 3× 0 + 0
= 2
g1(CPr2) = 2dd00(Pr2) + 3dd′0(Pr2) + 3d̃d′0(Pr2) + 4
−→
dd′0(Pr2) + 4
←−
dd′0(Pr2)
+ 2
←−
dd′′0(Pr2) + 4ds00(Pr2) + 2ds′0(Pr2) + 4sd00(Pr2) + 2sd′0(Pr2)
+ 4ss00(Pr2) + dd′1(Pr2) + d̃d′1(Pr2) + 4
−→
dd′′1(Pr2) + 2
←−
dd′′1(Pr2)
+ 2ds′1(Pr2) + 2sd′1(Pr2) + 4ss11(Pr2) + 3ss21(Pr2) + ss22(Pr2)
= 2× 6 + 3× 1 + 3× 1 + 4× 0 + 4× 0 + 2× 0 + 4× 0 + 2× 0 + 4× 0
+ 2× 0 + 4× 0 + 46 + 46 + 4× 0 + 2× 0 + 2× 12 + 2× 12 + 4× 0
+ 3× 0 + 8
= 166
M. I. Poshni, I. F. Khan and J. L. Gross: Genus distributions of graphs. . . 143
g2(CPr2) = 2dd00(Pr2) + 2dd01(Pr2) + 3dd′1(Pr2) + 3d̃d′1(Pr2) + 4
−→
dd′1(Pr2)
+ 4
←−
dd′1(Pr2) + 2
←−
dd′′1(Pr2) + 4ds01(Pr2) + 2ds′1(Pr2) + 4sd01(Pr2)
+ 2sd′1(Pr2) + 4ss01(Pr2) + dd′2(Pr2) + d̃d′2(Pr2) + 4
−→
dd′′2(Pr2)
+ 2
←−
dd′′2(Pr2) + 2ds′2(Pr2) + 2sd′2(Pr2) + 4ss12(Pr2) + 3ss22(Pr2)
+ ss23(Pr2)
= 2× 6 + 2× 176 + 3× 46 + 3× 46 + 4× 22 + 4× 22 + 2× 0 + 4× 44
+ 2× 12 + 4× 44 + 2× 12 + 4× 0 + 400 + 400 + 4× 48 + 2× 48
+ 2× 544 + 2× 544 + 4× 72 + 3× 8 + 288
= 5080
g3(CPr2) = 2dd01(Pr2) + 2dd02(Pr2) + 3dd′2(Pr2) + 3d̃d′2(Pr2) + 4
−→
dd′2(Pr2)
+ 4
←−
dd′2(Pr2) + 2
←−
dd′′2(Pr2) + 4ds02(Pr2) + 2ds′2(Pr2) + 4sd02(Pr2)
+ 2sd′2(Pr2) + 4ss02(Pr2) + dd′3(Pr2) + d̃d′3(Pr2) + 4
−→
dd′′3(Pr2)
+ 2
←−
dd′′3(Pr2) + 2ds′3(Pr2) + 2sd′3(Pr2) + 4ss13(Pr2) + 3ss23(Pr2)
+ ss24(Pr2)
= 2× 176 + 2× 704 + 3× 400 + 3× 400 + 4× 256 + 4× 256 + 2× 48
+ 4× 800 + 2× 544 + 4× 800 + 2× 544 + 4× 320 + 0 + 0 + 4× 0
+ 2× 0 + 2× 1920 + 2× 1920 + 4× 1664 + 3× 288 + 0
= 31360
g4(CPr2) = 2dd02(Pr2) + 2dd03(Pr2) + 3dd′3(Pr2) + 3d̃d′3(Pr2) + 4
−→
dd′3(Pr2)
+ 4
←−
dd′3(Pr2) + 2
←−
dd′′3(Pr2) + 4ds03(Pr2) + 2ds′3(Pr2) + 4sd03(Pr2)
+ 2sd′3(Pr2) + 4ss03(Pr2) + dd′4(Pr2) + d̃d′4(Pr2) + 4
−→
dd′′4(Pr2)
+ 2
←−
dd′′4(Pr2) + 2ds′4(Pr2) + 2sd′4(Pr2) + 4ss14(Pr2) + 3ss24(Pr2)
+ ss25(Pr2)
= 2× 704 + 2× 0 + 3× 0 + 3× 0 + 4× 0 + 4× 0 + 2× 0 + 4× 384
+ 2× 1920 + 4× 384 + 2× 1920 + 4× 1888 + 0 + 0 + 4× 0 + 2× 0
+ 2× 0 + 2× 0 + 4× 2304 + 3× 0 + 0
= 28928
LetKPrn be the contra-self-amalgamated closed chain of n copies of ∆G, as illustrated
in Figure 15. We calculate genus distributions for contra-self-amalgamated closed chains
KPr1 and KPr2 by substituting values from Table 2 into Equation (2.22) as follows:
Figure 15: Contra-pasted closed chains of copies of a triangular prism graph.
144 Ars Math. Contemp. 5 (2012) 127–148
g0(KPr1) =
−→
dd′0(Pr1) +
←−
dd′0(Pr1) + 4
←−
dd′′0(Pr1) + 2
−→
dd′′0(Pr1) + 2ds′0(Pr1)
+ 2sd′0(Pr1) + 4ss10(Pr1) + 3ss20(Pr1) + ss21(Pr1)
= 0 + 0 + 4× 0 + 2× 0 + 2× 0 + 2× 0 + 4× 0 + 3× 0 + 2
= 2
g1(KPr1) = 2dd00(Pr1) + 3
−→
dd′0(Pr1) + 3
←−
dd′0(Pr1) + 4dd′0(Pr1) + 4d̃d′0(Pr1)
+ 2
−→
dd′′0(Pr1) + 4ds00(Pr1) + 2ds′0(Pr1) + 4sd00(Pr1) + 2sd′0(Pr1)
+ 4ss00(Pr1) +
−→
dd′1(Pr1) +
←−
dd′1(Pr1) + 4
←−
dd′′1(Pr1) + 2
−→
dd′′1(Pr1)
+ 2ds′1(Pr1) + 2sd′1(Pr1) + 4ss11(Pr1) + 3ss21(Pr1) + ss22(Pr1)
= 2× 0 + 3× 0 + 3× 0 + 4× 1 + 4× 1 + 2× 0 + 4× 0 + 2× 0 + 4× 0
+ 2× 0 + 4× 0 + 0 + 0 + 4× 0 + 2× 12 + 2× 8 + 2× 8 + 4× 0 + 3× 2
+ 0
= 70
g2(KPr1) = 2dd00(Pr1) + 2dd01(Pr1) + 3
−→
dd′1(Pr1) + 3
←−
dd′1(Pr1) + 4dd′1(Pr1)
+ 4d̃d′1(Pr1) + 2
−→
dd′′1(Pr1) + 4ds01(Pr1) + 2ds′1(Pr1) + 4sd01(Pr1)
+ 2sd′1(Pr1) + 4ss01(Pr1) +
−→
dd′2(Pr1) +
←−
dd′2(Pr1) + 4
←−
dd′′2(Pr1)
+ 2
−→
dd′′2(Pr1) + 2ds′2(Pr1) + 2sd′2(Pr1) + 4ss12(Pr1) + 3ss22(Pr1)
+ ss23(Pr1)
= 2× 0 + 2× 0 + 3× 0 + 3× 0 + 4× 0 + 4× 0 + 2× 12 + 4× 4 + 2× 8
+ 4× 4 + 2× 8 + 4× 0 + 0 + 0 + 4× 0 + 2× 0 + 2× 0 + 2× 0
+ 4× 24 + 3× 0 + 0
= 184
g0(KPr2) =
−→
dd′0(Pr2) +
←−
dd′0(Pr2) + 4
←−
dd′′0(Pr2) + 2
−→
dd′′0(Pr2) + 2ds′0(Pr2)
+ 2sd′0(Pr2) + 4ss10(Pr2) + 3ss20(Pr2) + ss21(Pr2)
= 0 + 0 + 4× 0 + 2× 0 + 2× 0 + 2× 0 + 4× 0 + 3× 0 + 0
= 0
g1(KPr2) = 2dd00(Pr2) + 3
−→
dd′0(Pr2) + 3
←−
dd′0(Pr2) + 4dd′0(Pr2) + 4d̃d′0(Pr2)
+ 2
−→
dd′′0(Pr2) + 4ds00(Pr2) + 2ds′0(Pr2) + 4sd00(Pr2) + 2sd′0(Pr2)
+ 4ss00(Pr2) +
−→
dd′1(Pr2) +
←−
dd′1(Pr2) + 4
←−
dd′′1(Pr2) + 2
−→
dd′′1(Pr2)
+ 2ds′1(Pr2) + 2sd′1(Pr2) + 4ss11(Pr2) + 3ss21(Pr2) + ss22(Pr2)
= 2× 6 + 3× 0 + 3× 0 + 4× 1 + 4× 1 + 2× 0 + 4× 0 + 2× 0 + 4× 0
+ 2× 0 + 4× 0 + 22 + 22 + 4× 0 + 2× 0 + 2× 12 + 2× 12 + 4× 0
+ 3× 0 + 8
= 120
M. I. Poshni, I. F. Khan and J. L. Gross: Genus distributions of graphs. . . 145
g2(KPr2) = 2dd00(Pr2) + 2dd01(Pr2) + 3
−→
dd′1(Pr2) + 3
←−
dd′1(Pr2) + 4dd′1(Pr2)
+ 4d̃d′1(Pr2) + 2
−→
dd′′1(Pr2) + 4ds01(Pr2) + 2ds′1(Pr2) + 4sd01(Pr2)
+ 2sd′1(Pr2) + 4ss01(Pr2) +
−→
dd′2(Pr2) +
←−
dd′2(Pr2) + 4
←−
dd′′2(Pr2)
+ 2
−→
dd′′2(Pr2) + 2ds′2(Pr2) + 2sd′2(Pr2) + 4ss12(Pr2) + 3ss22(Pr2)
+ ss23(Pr2)
= 2× 6 + 2× 176 + 3× 22 + 3× 22 + 4× 46 + 4× 46 + 2× 0 + 4× 44
+ 2× 12 + 4× 44 + 2× 12 + 4× 0 + 256 + 256 + 4× 48 + 2× 48
+ 2× 544 + 2× 544 + 4× 72 + 3× 8 + 288
= 4840
g3(KPr2) = 2dd01(Pr2) + 2dd02(Pr2) + 3
−→
dd′2(Pr2) + 3
←−
dd′2(Pr2) + 4dd′2(Pr2)
+ 4d̃d′2(Pr2) + 2
−→
dd′′2(Pr2) + 4ds02(Pr2) + 2ds′2(Pr2) + 4sd02(Pr2)
+ 2sd′2(Pr2) + 4ss02(Pr2) +
−→
dd′3(Pr2) +
←−
dd′3(Pr2) + 4
←−
dd′′3(Pr2)
+ 2
−→
dd′′3(Pr2) + 2ds′3(Pr2) + 2sd′3(Pr2) + 4ss13(Pr2) + 3ss23(Pr2)
+ ss24(Pr2)
= 2× 176 + 2× 704 + 3× 256 + 3× 256 + 4× 400 + 4× 400 + 2× 48
+ 4× 800 + 2× 544 + 4× 800 + 2× 544 + 4× 320 + 0 + 0 + 4× 0
+ 2× 0 + 2× 1920 + 2× 1920 + 4× 1664 + 3× 288 + 0
= 31648
g4(KPr2) = 2dd02(Pr2) + 2dd03(Pr2) + 3
−→
dd′3(Pr2) + 3
←−
dd′3(Pr2) + 4dd′3(Pr2)
+ 4d̃d′3(Pr2) + 2
−→
dd′′3(Pr2) + 4ds03(Pr2) + 2ds′3(Pr2) + 4sd03(Pr2)
+ 2sd′3(Pr2) + 4ss03(Pr2) +
−→
dd′4(Pr2) +
←−
dd′4(Pr2) + 4
←−
dd′′4(Pr2)
+ 2
−→
dd′′4(Pr2) + 2ds′4(Pr2) + 2sd′4(Pr2) + 4ss14(Pr2) + 3ss24(Pr2)
+ ss25(Pr2)
= 2× 704 + 2× 0 + 3× 0 + 3× 0 + 4× 0 + 4× 0 + 2× 0 + 4× 384
+ 2× 1920 + 4× 384 + 2× 1920 + 4× 1888 + 0 + 0 + 4× 0
+ 2× 0 + 2× 0 + 2× 0 + 4× 2304 + 3× 0 + 0
= 28928
In a similar manner, we can compute the genus distributions for CPrn and KPrn for
higher values of n. We conclude this section by giving the partitioned genus distribution of
Pr3 in Table 3 and listing the genus distributions of CPr3 and KPr3 obtained similarly.
146 Ars Math. Contemp. 5 (2012) 127–148
Table 3: Genus distributions of the open chain Pr3 of 3 copies of ∆G.
Prn Pr3
k 0 1 2 3 4 5 6
dd0k 30 2080 40000 211840 67584 0 0
dd′k 1 82 2608 27104 38400 0 0
d̃d′k 1 82 2608 27104 38400 0 0
−→
dd′k 0 46 2176 25376 38400 0 0
←−
dd′k 0 46 2176 25376 38400 0 0
−→
dd′′k 0 0 0 288 3456 0 0
←−
dd′′k 0 0 0 288 3456 0 0
ds0k 0 212 11744 149568 336896 36864 0
−→
ds′k 0 6 640 17664 113792 92160 0
←−
ds′k 0 6 640 17664 113792 92160 0
sd0k 0 212 11744 149568 336896 36864 0
−→
sd′k 0 6 640 17664 113792 92160 0
←−
sd′k 0 6 640 17664 113792 92160 0
ss0k 0 0 1496 61728 393728 417792 0
ss1k 0 0 72 6144 112000 411648 221184
ss2k 0 0 0 32 3456 0 0
gk 32 2784 77184 755072 1866240 1271808 221184
g0(CPr3) = 2 g1(CPr3) = 278 g2(CPr3) = 17480
g3(CPr3) = 447648 g4(CPr3) = 3920896 g5(CPr3) = 8667648
g6(CPr3) = 3723264
g0(KPr3) = 0 g1(KPr3) = 208 g2(KPr3) = 16688
g3(KPr3) = 445056 g4(KPr3) = 3924352 g5(KPr3) = 8667648
g6(KPr3) = 3723264
M. I. Poshni, I. F. Khan and J. L. Gross: Genus distributions of graphs. . . 147
5 Conclusions
This paper derives closed formulas for calculating the genus distributions of graphs result-
ing from co-self-amalgamation and contra-self-amalgamation of any double-edge-rooted
graph (G, e, f), where both the edges e and f have two 2-valent endpoints and the double-
root partitioned genus distribution of (G, e, f) is known. This enables one to make genus
distribution calculations for edge-amalgamated closed chains corresponding to many infi-
nite families of open chains. To illustrate this, we demonstrated how the genus distributions
of the circular ladder CL4 and the Möbius ladder ML4 can be calculated from the parti-
tioned genus distribution of the closed-end ladder L3. We also showed genus distribution
calculations of small co-self-pasted and contra-self-pasted closed chains of copies of the
triangular prism graph. In this manner, calculating genus distribution of arbitrarily large
closed chains consisting of identical copies of the same graph as well as well interleaved
copies of different graphs becomes tractible.
It would be interesting to know if open as well as closed chains of base graphs with
strongly unimodal genus distributions are unimodal. The results in this paper formulate
the genus distribution of closed chains as a linear combination of sub-partials of the corre-
sponding open chains. In turn, each of these sub-partials of an open chain is calculated as
a linear combination of convolutions of sub-partials of its constituent subgraphs. Although
convolutions of strongly unimodal sequences are strongly unimodal, linear combinations
of unimodal sequences need not be unimodal, unless the modes are sufficiently close to-
gether. This seems quite complicated, due to the large number of sub-partials. Neverthe-
less, the analysis of the closed-formulas presented in this paper may prove to be useful for
establishing structural results related to genus distributions such as the unimodality conjec-
ture. In particular, if the unimodality conjecture is false, the results could help construct a
counterexample to disprove the conjecture. Further opportunities for research also include
self-edge-amalgamation on root-edges with endpoints of higher-valence.
References
[1] C. P. Bonnington, M. J. Grannell, T. S. Griggs, and J. Širáň, Exponential families of non-
isomorphic triangulations of complete graphs, J. Combin. Theory (B) 78 (2000), 169–184.
[2] J. Chen, J. L. Gross and R. G. Rieper, Overlap matrices and total imbedding distributions,
Discrete Math. 128 (1994), 73–94.
[3] 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.
[4] M. L. Furst, J. L. Gross and R. Statman, Genus distribution for two classes of graphs, J. Com-
bin. Theory B 46 (1989), 22–36.
[5] L. Goddyn, R. B. Richter and J. Širáň, Triangular embeddings of complete graphs from graceful
labellings of paths, J. Combin. Theory (B) 97 (2007), 964–970.
[6] M. J. Grannell and T. S. Griggs, A lower bound for the number of triangular embeddings of
some complete graphs and complete regular tripartite graphs, J. Combin. Theory B 98 (2008),
637–650.
[7] J. L. Gross, Genus distribution of graphs under surgery: Adding edges and splitting vertices,
New York J. Math. 16 (2010), 161–178.
[8] J. L. Gross, Genus distribution of graph amalgamations: Self-pasting at root-vertices, Aus-
tralas. J. Combin. 49 (2011), 19–38.
148 Ars Math. Contemp. 5 (2012) 127–148
[9] J. L. Gross, Genus distributions of cubic outerplanar graphs, J. Graph. Algorithms Appl. 15
(2011), 295–316.
[10] J. L. Gross and M. L. Furst, Hierarchy for imbedding-distribution invariants of a graph,
J. Graph Theory 11 (1987), 205–220.
[11] 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.
[12] J. L. Gross, D. P. Robbins and T. W. Tucker, Genus distributions for bouquets of circles, J.
Combin. Theory B 47 (1989), 292–306.
[13] J. L. Gross and T. W. Tucker, Topological Graph Theory, Dover, 2001; (original edn. Wiley,
1987).
[14] 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.
[15] V. P. Korzhik and H.-J. Voss, Exponential families of non-isomorphic non-triangular orientable
genus embeddings of complete graphs, J. Combin. Theory B 86 (2002), 86–211.
[16] J. H. Kwak and J. Lee, Genus polynomials of dipoles, Kyungpook Math. J. 33 (1993), 115–125.
[17] J. H. Kwak and J. Lee, Enumeration of graph embeddings, Discrete Math. 135 (1994), 129–
151.
[18] J. H. Kwak and S. H. Shim, Total embedding distributions for bouquets of circles, Discrete
Math. 248 (2002), 93–108.
[19] L. A. McGeoch, Genus distribution for circular and Möbius ladders, technical report extracted
from PhD thesis, Carnegie-Mellon University, 1987.
[20] L. A. McGeoch, Algorithms for two graph problems: computing maximum-genus imbedding
and the two-server problem, PhD thesis, Carnegie-Mellon University, 1987.
[21] B. P. Mull, Enumerating the orientable 2-cell imbeddings of complete bipartite graphs, J. Graph
Theory 30 (1999), 77–90.
[22] M. I. Poshni, I. F. Khan, and J. L. Gross, Genus distribution of graphs under edge-
amalgamations, Ars Math. Contemp. 3 (2010), 69-86.
[23] M. I. Poshni, I. F. Khan, and J. L. Gross, Genus distributions of 4-regular outerplanar graphs,
Electon. J. Comb. 18 (2011), #P212.
[24] S. Stahl, Region distributions of graph embeddings and Stirling numbers, Discrete Math. 82
(1990), 57–78.
[25] S. Stahl, Permutation-partition pairs III: Embedding distributions of linear families of graphs,
J. Combin. Theory B 52 (1991), 191–218.
[26] S. Stahl, Region distributions of some small diameter graphs, Discrete Math. 89 (1991), 281–
299.
[27] E. H. Tesar, Genus distribution of Ringel ladders, Discrete Math. 216 (2000) 235–252.
[28] T. I. Visentin and S. W. Wieler, On the genus distribution of (p, q, n)-dipoles, Electronic J.
Combin. 14 (2007), R12.
[29] L. X. Wan and Y. P. Liu, Orientable embedding distributions by genus for certain types of
graphs, Ars Combin. 79 (2006), 97–105.
[30] L. X. Wan and Y. P. Liu, Orientable embedding genus distribution for certain types of graphs,
J. Combin. Theory B 47 (2008), 19–32.
[31] A. T. White, Graphs of Groups on Surfaces, North-Holland, 2001.