Also available at http://amc.imfm.si
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 3 (2010) 121–138
Genus distribution of graph amalgamations:
Pasting when one root has arbitrary degree
Imran F. Khan , Mehvish I. Poshni , Jonathan L. Gross
Columbia University, Department of Computer Science NY 10027, New York, USA
Received 2 July 2009, accepted 14 July 2010, published online 28 August 2010
Abstract
This paper concerns counting the imbeddings of a graph in a surface. In the first install-
ment of our current work, we showed how to calculate the genus distribution of an iterated
amalgamation of copies of a graph whose genus distribution is already known and is further
analyzed into a partitioned genus distribution (which is defined for a double-rooted graph).
Our methods were restricted there to the case with two 2-valent roots. In this sequel we
substantially extend the method in order to allow one of the two roots to have arbitrarily
high valence.
Keywords: Graph, genus distribution, vertex-amalgamation.
Math. Subj. Class.: 05C10
1 Introduction
We continue the development of methods for counting imbeddings of interesting families
of graphs in a range of surfaces. We are primarily concerned here with deriving recursions,
rather than with exact formulas. It may be helpful to precede the reading of this paper with
a light reading of [13].
By the vertex-amalgamation of the rooted graphs (G, t) and (H,u), we mean the graph
obtained from their disjoint union by merging the roots t and u. We denote the operation
of amalgamation by an asterisk, i.e.,
(G, t) ∗ (H,u) = (X,w)
where X is the amalgamated graph and w the merged root.
Terminology. We take a graph to be connected and an imbedding to be cellular and ori-
entable, unless it is evident from context that something else is intended. A graph need
E-mail addresses: imran@cs.columbia.edu (Imran F. Khan), poshni@cs.columbia.edu (Mehvish I. Poshni),
gross@cs.columbia.edu (Jonathan L. Gross)
Copyright c© 2010 DMFA Slovenije
122 Ars Math. Contemp. 3 (2010) 121–138
not be simple, i.e., it may have self-loops and multiple edges between two vertices. We
use the words degree and valence of a vertex to mean the same thing. Each edge has two
edge-ends, in the topological sense, even if it has only one endpoint.
Abbreviation. We abbreviate face-boundary walk as fb-walk.
Notation. The degree of a vertex y is denoted deg(y). The genus of a surface S is denoted
γ(S). The number of imbeddings of a graph G in the surface Si of genus i is denoted
gi. The sequence {gi(G) | i ≥ 0} is called the genus distribution of the graph G. The
terminology generally follows [15] and [1]. For additional background, see [3], [24], or
[34].
Prior work concerned with the number of imbeddings of a graph in a minimum-genus
surface includes [2], [8], [9], and [19]. Prior work concerned with counting imbeddings in
all orientable surfaces or in all surfaces includes [4], [5], [7], [12], [14], [20], [21], [22],
[23], [25], [27], [28], [29], [30], [31], [32], and [33].
Remark 1.1. Some of the calculations in this paper are quite intricate, and it appears that
taking the direct approach here to amalgamating two graphs at roots of arbitrarily high
degree might be formidable. We observe that a vertex of arbitrary degree can be split (by
inverse contraction) into two vertices of smaller degree. Effects on the genus distribution
that arise from splitting a vertex are described by [11].
Imbeddings induced by an amalgamation of two imbedded graphs
We say that the pair of imbeddings ιG : G → SG and ιH : H → SH induce the set of
imbeddings of X = G ∗ H whose rotations have the same cyclic orderings as in G and
H , and that this set of imbeddings of X is the result of amalgamating the two imbeddings
ιG : G→ SG and ιH : H → SH .
Proposition 1.2. For any two imbeddings ιG : G → SG and ιH : H → SH of graphs
into surfaces, the cardinality of the set of imbeddings of the amalgamated graph (X,w) =
(G, t) ∗ (H,u) whose rotation systems are consistent with the imbeddings ιG : G → SG
and ιH : H → SH is
(deg(u) + deg(t)− 1) ·
(
deg(t) + deg(u)− 2
deg(u)− 1
)
(1.1)
Proof. Formula (1.1) is a symmetrization of Formula (1.1) of [13].
In the amalgamation (G, t)∗(H,u) = (X,w), when one of the roots t and u is 1-valent,
the genus distribution of the resulting graph is easily derivable via bar-amalgamations (see
[12]). For the case where
deg(t) = deg(u) = 2,
methods for calculating the genus distribution are developed in [13]. For the purposes of
this paper, we assume that deg(t) = 2 and deg(u) = n ≥ 2. A pair of such imbeddings
ιG : G → SG and ιH : H → SH induce, in accordance with Formula (1.1), n2 + n
imbeddings of the amalgamated graph X . We observe that for each such imbedding ιX :
X → SX , we have
γ(SX) =
{
γ(SG) + γ(SH) or
γ(SG) + γ(SH) + 1
Imran F. Khan et al.: Genus distribution of graph amalgamations: Pasting when. . . 123
Terminology. The difference γ(SX)− (γ(SG) + γ(SH)) is called the genus increment of
the amalgamation, or more briefly, the genus increment or increment.
Proposition 1.3. In any vertex-amalgamation (G, t) ∗ (H,u) = (X,w) of two graphs, the
increment of genus lies within these bounds:⌈
1− deg(t)− deg(u)
2
⌉
≤ γ(SX)− (γ(SG) + γ(SH)) ≤
⌊
deg(t) + deg(u)− 2
2
⌋
Proof. See [13].
Double-rooted graphs
By a double-rooted graph (H,u, v) we mean a graph with two vertices designated as roots.
Double-rooted graphs were first introduced in [13] as they lend themselves natrually to
iterated amalgmation. For the purposes of this paper, root u is assumed to have degree n ≥
2, whereas root v is 2-valent. Our focus here, is the graph amalgamation (G, t) ∗ (H,u, v)
when deg(t) = deg(v) = 2 and deg(u) = n ≥ 2. This is illustrated in Figure 1.
Figure 1: (G, t) ∗ (H,u, v) when deg(t) = deg(v) = 2 and deg(u) = n ≥ 2.
When two single-rooted graphs are amalgamated, the amalgamated graph has the mer-
ged vertices of amalgamation as its root. If we iteratively amalgamate several single-rooted
graphs, we obtain a graph with a root of whose degree is the sum of the degrees of the
constituent roots. We use double-rooted graphs when we want to calculate the genus dis-
tribution of a chain of copies (as in §3 and §4) of the same graph (or of different graphs).
2 Double-root partials and productions
The genus distribution of the set of imbeddings of (X,w) = (G, t)∗ (H,u) whose rotation
systems are consistent with those of fixed imbeddings G → SG and H → SH , depends
only on γ(SG), γ(SH), and the respective numbers of faces of the imbeddings G → SG
and H → Sh in which the two vertices of amalgamation t and u lie. Accordingly, we
partition the imbeddings of a single-rooted graph (G, t) with deg(t) = 2 in a surface of
genus i into the subset of type-di imbeddings, in which root t lies on two distinct fb-walks,
and the subset of type-si imbeddings, in which root t occurs twice on the same fb-walk.
Moreover, we define
di(G, t) = the number of imbeddings of type-di, and
si(G, t) = the number of imbeddings of type-si.
124 Ars Math. Contemp. 3 (2010) 121–138
Thus,
gi(G, t) = di(G, t) + si(G, t).
The numbers di(G, t) and si(G, t) are called single-root partials. The sequences {di(G, t)|
i ≥ 0} and {si(G, t) | i ≥ 0} are called partial genus distributions.
Since deg(u) = n in a double-rooted graph (H,u, v), there are n face corners incident
at u (i.e., u occurs n times in the fb-walks — we will call them u-corners from now on),
some or all of which might belong to the same face.
Suppose further that the n occurrences of root u in fb-walks of different faces are dis-
tributed according to the partition p1p2 · · · pr of n (where r is the number of faces incident
at root u). For each such partition p1p2 · · · pr, we define the following double-root partials
of the genus distribution of a graph (H,u, v), such that root u is n-valent and root v is
2-valent:
fp1p2···prdi = the number of imbeddings of H such that the n occurrences of
root u are distributed according to the partition p1p2 · · · pr, and
the 2 occurrences of v lie on two different fb-walks.
fp1p2···prsi = the number of imbeddings of H such that the n occurrences of
root u are distributed according to the partition p1p2 · · · pr, and
the 2 occurrences of v lie on the same fb-walk.
Notation. We write the partition p1p2 · · · pr of an integer in non-ascending order.
A production for an amalgamation
(G, t) ∗ (H,u, v) = (X, v)
of a single-rooted graph (G, t) with a double-rooted graph (H,u, v) (where deg(t) =
deg(v) = 2, and deg(u) ≥ 2) is an expression of the form
pi(G, t) ∗ qj(H,u, v) −→ α1 di+j(G ∗H, v) + α2 di+j+1(G ∗H, v)
+α3 si+j(G ∗H, v) + α4 si+j+1(G ∗H, v)
where pi is a single-root partial and qj is a double-root partial, and where α1, α2, α3, and
α4 are integers. It means that amalgamation of a type-pi imbedding of graph (G, u) and
a type-qj imbedding of graph (H,u, v) induces a set of α1 type-di+j , α2 type-di+j+1, α3
type-si+j , and α4 type-si+j+1 imbeddings of G ∗ H . We often write such a rule in the
form
pi ∗ qj −→ α1 di+j + α2 di+j+1 + α3 si+j + α4 si+j+1
Sub-partials of fp1p2···prdi
In the course of developing productions for amalgamating a single-rooted graph (G, t) to a
double-rooted graph (H,u, v), we shall discover that we sometimes need to refine a double-
root partial into sub-partials. The following two types of numbers are the sub-partials of
fp1p2···prdi:
Imran F. Khan et al.: Genus distribution of graph amalgamations: Pasting when. . . 125
fp1p2···prd
′
i = the number of type-fp1p2···prdi imbeddings such that at
most one of the r fb-walks incident at u is the same as
one of the two fb-walks incident at v;
fp1p2···prd
(pl,pm)
i = the number of type-fp1p2···prdi imbeddings such that the
two fb-walks (corresponding to subscripts l and m) inci-
dent at v have pl and pm occurrences of u, where l < m
(so that, in general, pl ≥ pm), and r > 1.
Note that the value of the latter sub-partial of a graph (H,u, v) would be the same for any
two pairs (pa, pb) and (pl, pm) such that (pl, pm) = (pa, pb). Also note that, in general, we
have
fp1p2···prdi = fp1p2···prd
′
i +
∑
over all distinct
pairs (pl,pm)
with l<m
fp1p2···prd
(pl,pm)
i
Example 2.1. For instance, f112d4 = f112d′4 + f112d
(1,1)
4 + f112d
(1,2)
4 , since (1, 1) and
(1, 2) are the distinct pairs.
Lemma 2.2. Let x represent a face of an imbedded graph (H,u, v) with px > 0 u-corners.
There are px(px + 1) ways to insert two edge-ends into the u-corners of this face.
Proof. Since there are px u-corners, there are px choices for the location of the first edge-
end. After the first edge-end is inserted, the number of u-corners is px + 1. Thus, there are
px +1 choices for the second edge-end. Hence, there are a total of px(px +1) choices (see
Figure 2).
Figure 2: Since px = 5, there are 30 = 5 ∗ 6 ways to insert two edge-ends into the
u-corners of this face.
Lemma 2.3. Let x and y be two faces of an imbedded graph (H,u, v), with px > 0 and
py > 0 u-corners, respectively. There are 2pxpy ways to insert two edge-ends at root u,
such that one edge-end is in face x and the other in face y.
Proof. There are px choices for the edge-end that is inserted into face x, and for each such
choice, there are py choices for the other edge-end (see Figure 3). Since either of the two
edge-ends can be the one that is inserted into face x, we need to multiply pxpy by 2.
126 Ars Math. Contemp. 3 (2010) 121–138
Figure 3: Since px = 3 and py = 4, there are 24 = 2 · 3 · 4 ways to insert two edge-ends
with one edge-end in each of the two faces.
Theorem 2.4. Let p1p2 · · · pr be a partition of an integer n ≥ 2. Suppose that a type-di
imbedding of a single-rooted graph (G, t) is amalgamated to a type-fp1p2···prdj imbedding
of a double-rooted graph (H,u, v), with deg(v) = deg(t) = 2 and deg(u) = n. Then the
following production holds:
di ∗ fp1p2···prd′j −→
(
r∑
x=1
px(px + 1)
)
di+j
+
(
r∑
x=1
r∑
y=x+1
2pxpy
)
di+j+1 (2.1)
Proof. Since at most one of the r faces incident at root u of H is incident at root v of H ,
it follows that no matter how the root t of G is amalgamated to u, at most one of the two
faces incident at v are affected by this amalgamation. It follows that in the amalgamated
graph the two occurrences of v remain on two different faces. There are two cases:
case i. Suppose that both edge-ends incident at root t of graph G are placed into one of
the r faces of graph H incident at u. Then no new handle is needed, and thus, the genus
increment is 0. The coefficient
∑r
x=1 px(px + 1) of di+j counts the number of ways this
can happen. The summation goes from 1 to r, since we can put the two edge-ends incident
at t into any of the r faces. The term px(px + 1) follows from Lemma 2.2.
case ii. Suppose that the two edge-ends incident at root t of graph G are placed into two
different faces incident at u. This would necessitate adding a handle — resulting in a genus
increment of 1. The coefficient
∑r
x=1
∑r
y=x+1 2pxpy of di+j+1 counts the number of
ways this can happen, by Lemma 2.3.
Theorem 2.5. Let p1p2 · · · pr be a partition of an integer n ≥ 2, and let (pl, pm) be a pair
such that 1 ≤ l < m ≤ r. Suppose that a type-di imbedding of a single-rooted graph (G, t)
is amalgamated to a type-fp1p2···prd
(pl,pm)
j imbedding of a double-rooted graph (H,u, v),
with deg(v) = deg(t) = 2 and deg(u) = n. Then the following production holds:
di ∗ fp1p2···prd
(pl,pm)
j −→
(
r∑
x=1
px(px + 1)
)
di+j
+
((
r∑
x=1
r∑
y=x+1
2pxpy
)
− 2plpm
)
di+j+1
+ 2plpmsi+j+1 (2.2)
Imran F. Khan et al.: Genus distribution of graph amalgamations: Pasting when. . . 127
Proof. Let ϕl and ϕm be the two faces incident at root u that are also incident at v, with
u occurring pl times on fb-walk of face ϕl, and pm times on fb-walk of face ϕm. We note
that unless we place one edge-end incident at root t of graph (G, t) into face ϕl and the
other edge-end into face ϕm, at most one of the two faces ϕl and ϕm is affected by this
amalgamation. Thus, case i remains the same as in Theorem 2.4. The first term of the
Production (2.2) reflects this similarity. Moreover, case ii remains the same as in Theorem
2.4, unless x and y correspond to the faces ϕl and ϕm, which is why we subtract 2plpm
from the second sum in Production (2.2). If x and y correspond to the faces ϕl and ϕm,
then as a result of the amalgamation, the two faces (ϕl and ϕm) combine to become one
face having both occurrences of v in its boundary (see Figure 4). The third term of the
production reflects this.
Figure 4: Here pl = 3 and pm = 4. Amalgamation combines the two faces, and the
resultant face contains both occurrences of v.
Notation. We sometimes use the shorthand fp1p2···prd•j in place of fp1p2···prdj , to empha-
size the absence of any superscript after dj .
Theorem 2.6. Let p1p2 · · · pr be a partition of an integer n ≥ 2. Suppose that a type-si
imbedding of a single-rooted graph (G, t) is amalgamated to a type-fp1p2···prd
•
j imbedding
of a double-rooted graph (H,u, v), with deg(v) = deg(t) = 2 and deg(u) = n. Then the
following production holds:
si ∗ fp1p2···prd•j −→ (n2 + n)di+j (2.3)
where the coefficient n2 + n =
(
n+1
n
)
follows from Proposition 1.2.
Proof. Suppose that in a type-fp1p2···prd
•
j imbedding of graph (H,u, v), the two occur-
rences of root-vertex v lie on on two different fb-walks W1 and W2 that may or may not
contain the root-vertex u. Suppose further that the two occurrences of root-vertex t of
graph (G, t) lie on fb-walk X . The two occurrences of root-vertex v continue being on two
different fb-walks after the operation of vertex amalgamation, unless the fb-walks W1 and
W2 combine with the fb-walkX under amalgamation into a single fb-walk. But this cannot
happen when the imbedding of (G, t) is a type-si imbedding, since a reduction of two faces
forces the Euler characteristic to be of odd parity, which is not possible. Thus, there is no
genus-increment and all n2 + n resulting imbeddings are type-di+j imbeddings.
128 Ars Math. Contemp. 3 (2010) 121–138
Sub-partials of fp1p2···prsi
To define the sub-partials of fp1p2···prsi we need the concept of strands, which was intro-
duced and used extensively in [13]. When two imbeddings are amalgamated, these strands
recombine with other strands to form new fb-walks.
Definition 2.7. We define a u-strand of an fb-walk of a rooted graph (H,u, v) to be a
subwalk that starts and ends with the root vertex u, such that u does not appear in the
interior of the subwalk.
The following two types of numbers are the relevant sub-partials of the partial fp1p2···prsi
for graph (H,u, v):
fp1p2···prs
′
i = the number of type-fp1p2···prsi imbeddings of H such
that the two occurrences of v lie in at most one u-strand.
fp1p2···prs
(pl,c)
i = the number of type-fp1p2···prsi imbeddings of H such
that the two occurrences of v lie in two different u-
strands of the fb-walk that is represented by pl, and such
that there are q ≥ 1 intermediate u-corners between
the two occurrences of v. We take c to be equal to
min(q, pl − q), i.e., equal to the smaller number of inter-
mediate u-corners between the two occurrences of root-
vertex v.
Note that the last sub-partial would be the same for any other pair (pa, c) such that pa = pl.
Theorem 2.8. Let p1p2 · · · pr be a partition of an integer n ≥ 2. Suppose that a type-di
imbedding of a single-rooted graph (G, t) is amalgamated to a type-fp1p2···prs
′
j imbedding
of a double-rooted graph (H,u, v), with deg(v) = deg(t) = 2 and deg(u) = n. Then the
following production holds:
di ∗ fp1p2···prs′j −→
(
r∑
x=1
px(px + 1)
)
si+j
+
(
r∑
x=1
r∑
y=x+1
2pxpy
)
si+j+1 (2.4)
Proof. Since both occurrences of root v of H lie in at most one u-strand of one of the r
fb-walks, it follows that regardless of how the u-strands recombine in the amalgamation
process, these two occurrences remain on that same u-strand; thus, in all of the resultant
imbeddings, the two occurrences of v are on the same fb-walk. As discussed in the proof
of Theorem 2.4, there are
∑r
x=1 px(px + 1) imbeddings that do not result in any genus-
increment (corresponding to both edge-ends at t being inserted into the same face at u),
whereas there are
∑r
y=x+1 2pxpy imbeddings that result in a genus increment of 1 (corre-
sponding to inserting both edge-ends at t into the different faces at u).
Theorem 2.9. Let p1p2 · · · pr be a partition of an integer n ≥ 2. Then for each distinct
pl, with l ∈ {1, · · · , r}, and for each integer c in the integer interval [1,
⌊
pl
2
⌋
], when a
Imran F. Khan et al.: Genus distribution of graph amalgamations: Pasting when. . . 129
type-di imbedding of a single-rooted graph (G, t) is amalgamated to a type-fp1p2···prs
(pl,c)
j
imbedding of a double-rooted graph (H,u, v), with deg(v) = deg(t) = 2 and deg(u) = n,
the following production holds:
di ∗ fp1p2···prs
(pl,c)
j −→
((
r∑
x=1
px(px + 1)
)
− pl(pl + 1)
)
si+j
+ 2c(pl − c) di+j
+ [c(c+ 1) + (pl − c)(pl − c+ 1)] si+j
+
(
r∑
x=1
r∑
y=x+1
2pxpy
)
si+j+1 (2.5)
Proof. Let ϕl be the face corresponding to pl, and let w1 and w2 be the two (different)
u-strands that contain the two occurrences of root v of H (with c intermediate u-corners
between the two occurrences of v). It follows that unless the two edge-ends incident at root
t of G are both placed into the face ϕl, the two occurrences of root v will lie on the same
fb-walk after amalgamation. The first and last terms of the production reflect this.
Now we consider the case when the two edge-ends incident at root t of graph (G, t) are
both placed into the face ϕl. Let estart1 and estart2 be the initial edge-ends of u-strands
w1 and w2, similarly let eend1 and eend2 be the terminal edge-ends of u-strands w1 and w2
(we consider that a u-strand starts and ends at root u). This is illustrated in Figure 5.
Figure 5: fb-walk of a type-fp1p2···prs
(pl,c)
j imbedding.
It is clear that in the fb-walk of the face ϕl, these four edge-ends appear in estart1 , eend1 ,
estart2 , eend2 cyclic order. If one of the two edge-ends incident at root t is placed between
eend1 and estart2 and the other between eend2 and estart1 , then after the strands are recom-
bined, one of the u-strands containing one occurrence of root v clearly recombines with the
one t-strand of (G, t) to make a new face (see Figure 6, left).
It follows that in this case the two occurrences of root v will lie on two different faces.
Since there are a total of pl u-corners in face ϕl, and there are c intermediate u-corners
between the two occurrences of root v of graph (H,u, v), there are 2c(pl − c) ways in all
130 Ars Math. Contemp. 3 (2010) 121–138
Figure 6: The two ways of inserting t-strands.
of inserting the two edge-ends incident at root t of graph (G, t) in this way. We multiply by
2 since either of the two edge-ends can be chosen as the first edge-end. The second term of
the production reflects this case.
If both of the edge-ends incident at root t are placed between eend1 and estart2 , or
between eend2 and estart1 , then the two occurrences of root v lie on the same face after
u-strands and t-strands are recombined (see Figure 6, right). There are c(c + 1) + (pl −
c)(pl − c + 1) ways this can happen, since there are c and pl − c intermediate u-corners
between w1 and w2.
Notation. We sometimes use the shorthand fp1p2···prs•j in place of fp1p2···prsj , to empha-
size the absence of any superscript after sj .
Theorem 2.10. Let p1p2 · · · pr be a partition of an integer n ≥ 2. Suppose that a type-si
imbedding of a single-rooted graph (G, t) is amalgamated to a type-fp1p2···prsj imbedding
of a double-rooted graph (H,u, v), with deg(v) = deg(t) = 2 and deg(u) = n. Then the
following production holds:
si ∗ fp1p2···prs•j −→ (n2 + n)si+j (2.6)
Proof. Since the two occurrences of root v of H lie on the same fb-walk. One necessary
condition for the operation of vertex amalgamation to change this is that both edge-ends at
root t of G are inserted into that face. However, since both occurrences of root t are on the
same fb-walk, both ends of each t-strand lie in the same u-corner of that face, as illustrated
in Figure 7. This implies that no new handle is needed as a result of the amalgamation.
Thus, there is no genus-increment.
Corollary 2.11. Let (X, v) = (G, t)∗(H,u, v), where deg(v) = deg(t) = 2 and deg(u) =
n for n ≥ 2. Then for
αp1p2···pr =
r∑
x=1
px(px + 1) and βp1p2···pr =
r∑
x=1
r∑
y=x+1
2pxpy
we have
Imran F. Khan et al.: Genus distribution of graph amalgamations: Pasting when. . . 131
Figure 7: Even after the amalgamation, the two occurrences of v remain on the same fb-
walk.
dk(X) =
∑
over all partitions
p1p2···pr of n
[ k∑
i=0
αp1p2···pr dk−ifp1p2···prd
′
i
+
k−1∑
i=0
βp1p2···pr dk−i−1fp1p2···prd
′
i
+
k∑
i=0
∑
over all
distinct (pl,pm)
l <m
αp1p2···pr dk−ifp1p2···prd
(pl,pm)
i
+
k−1∑
i=0
∑
over all
distinct (pl,pm)
l <m
(βp1p2···pr − 2plpm) dk−i−1fp1p2···prd
(pl,pm)
i
+
k∑
i=0
(n2 + n) sk−ifp1p2···prd
•
i
+
k∑
i=0
∑
over all
distinct pl
b pl2 c∑
c=1
2c(pl − c) dk−ifp1p2···prs
(pl,c)
i
]
(2.7)
Proof. This equation is derived from Theorems 2.4, 2.5, 2.6 and 2.9 by a routine transpo-
sition of the productions that have the single-root partial d on their right-hand-side.
Corollary 2.12. Let (X, v) = (G, t)∗(H,u, v), where deg(v) = deg(t) = 2 and deg(u) =
n for n ≥ 2. Then for
αp1p2···pr =
r∑
x=1
px(px + 1) and βp1p2···pr =
r∑
x=1
r∑
y=x+1
2pxpy
132 Ars Math. Contemp. 3 (2010) 121–138
we have
sk(X) =
∑
over all partitions
p1p2···pr of n
[ k∑
i=0
αp1p2···pr dk−ifp1p2···prs
′
i
+
k−1∑
i=0
βp1p2···pr dk−i−1fp1p2···prs
′
i
+
k−1∑
i=0
∑
over all
distinct (pl,pm)
l <m
2plpm dk−i−1fp1p2···prd
(pl,pm)
i
+
k∑
i=0
∑
over all
distinct pl
b pl2 c∑
c=1
(
c(c+ 1) + (pl − c)(pl − c+ 1)
+ αp1p2···pr − pl(pl + 1)
)
dk−ifp1p2···prs
(pl,c)
i
+
k−1∑
i=0
∑
over all
distinct pl
b pl2 c∑
c=1
βp1p2···pr dk−i−1fp1p2···prs
(pl,c)
i
+
k∑
i=0
(n2 + n) sk−ifp1p2···prs
•
i
]
(2.8)
Proof. This equation is derived from Theorems 2.5, 2.8, 2.9 and 2.10 by a routine transpo-
sition of the productions that have the single-root partial s on their right-hand-side.
Remark 2.13. In writing Recursions 2.7 and 2.8, we have suppressed indication of graphs
G and H as arguments, in order that they not occupy too many lines. In the examples
to follow, we see how restriction of these recursions to particular genus distributions of
interest greatly simplifies them. The reason for placing the index variable i of each sum
with the second factor, rather than the first, also becomes clear in the applications.
3 Open chains of copies of K4
We can specify a sequence of open chains of copies of a double-rooted graph (G, u, v)
recursively.
(X1, t1) = (G, v) (suppressing co-root u) (3.1)
(Xm, tm) = (Xm−1, tm−1) ∗ (G, u, v) for m ≥ 1 (3.2)
For example, consider a chain of copies of the graph K4 with one edge subdivided as in
Figure 8. We observe that each of the amalgamations results in a vertex of degree 5.
By face-tracing the imbeddings of K4, we obtain Table 1.
By using Recurrences (2.7) and (2.8) for deg(u) = n = 3, and the values from Table 1,
Imran F. Khan et al.: Genus distribution of graph amalgamations: Pasting when. . . 133
Figure 8: Xm is an open chain of m copies of K4.
k f111d
′
k f21d
(2,1)
k f21s
(2,1)
k f3d
′
k dk sk gk
0 2 0 0 0 2 0 2
1 0 6 6 2 8 6 14
Table 1: Nonzero partials of (G, u, v).
we obtain the following two recurrences, for m ≥ 2, k ≥ 0:
dk(Xm) = 12dk(Xm−1) + 24sk(Xm−1) + 96dk−1(Xm−1) + 96sk−1(Xm−1) (3.3)
sk(Xm) = 48dk−2(Xm−1) + 36dk−1(Xm−1) + 72sk−1(Xm−1) (3.4)
Another way of obtaining these recurrences without having to use Recurrences (2.7) and
(2.8), is to first list all productions that are relevant for the example at hand (i.e. correspond-
ing to the non-zero double-root partials) using Theorems 2.4–2.10; we list the productions
for this example in Table 2. We can then transpose these productions, and use the values
of double-root partials from Table 1 on the transposed productions to come up with the
desired recurrences.
di ∗ f111d′j −→ 6di+j + 6di+j+1
si ∗ f111d•j −→ 12di+j
di ∗ f21d(2,1)j −→ 8di+j + 4si+j+1
di ∗ f21s(2,1)j −→ 2di+j + 6si+j + 4si+j+1
si ∗ f21d•j −→ 12di+j
si ∗ f21s•j −→ 12si+j
di ∗ f3d′j −→ 12di+j
si ∗ f3d•j −→ 12di+j
Table 2: The non-zero productions when deg(u) = 3.
Using these recurrences and the values of single-root partials in Table 1, we obtain the
values of single-root partials for X2, that are listed in Table 3. We can then use values of
the partials for X2 to obtain the values of single-root partials for X3, also listed in Table 3.
We can iterate this to obtain the genus distribution of Xm for any value of m.
134 Ars Math. Contemp. 3 (2010) 121–138
X2 X3
k dk sk gk dk sk gk
0 24 0 24 288 0 288
1 432 72 504 9216 864 10080
2 1344 816 2160 84096 21888 105984
3 0 384 384 216576 127872 344448
4 36864 92160 129024
Table 3: Single-root partials of X2 and X3.
4 Another example
As another illustration of the method, we compute the recurrences for the open chains of a
graph (G, s, t) in which deg(u) = n = 6 (see Figure 9). Where, as in previous example,
X1 is the graph G with root s suppressed.
X1 X2 X3
Figure 9: Xm is an open chain of m copies of G.
By face-tracing the imbeddings of (G, u, v), we obtain Table 4.
type k = 0 k = 1
f51d
(5,1) 0 16
f2211d
(2,2) 8 0
f2211d
(2,1) 16 0
f42s
(4,2) 0 8
f42d
(4,2) 0 16
f33d
(3,3) 0 8
f3111d
(3,1) 16 0
f51s
(5,2) 0 32
dk 40 40
sk 0 40
gk 40 80
Table 4: Nonzero partials of (G, u, v).
Using Recurrences (2.7) and (2.8), we obtain the following two recurrences for m ≥
Imran F. Khan et al.: Genus distribution of graph amalgamations: Pasting when. . . 135
2, k ≥ 0:
dk(Xm) = 672dk(Xm−1) + 1680sk(Xm−1)
+ 2352dk−1(Xm−1) + 1680sk−1(Xm−1) (4.1)
sk(Xm) = 1008dk−2(Xm−1) + 1008dk−1(Xm−1) + 1680sk−1(Xm−1) (4.2)
Table 5 records the values that these recurrences give us for X2 and X3.
X2 X3
k dk sk gk dk sk gk
0 26880 0 26880 18063360 0 18063360
1 188160 40320 228480 257402880 27095040 284497920
2 161280 147840 309120 867041280 284497920 1151539200
3 0 40320 40320 695439360 600606720 1296046080
4 67737600 230307840 298045440
Table 5: Single-root partials of X2 and X3.
5 Conclusions
Results in this paper enable us to compute genus distributions of open chains in which the
degree of the amalgamated vertex can be arbitrarily large, a significant improvement from
the previous results where it was limited to being 4-valent.
Using the methods developed in this paper, one can compute the following:
• the genus distribution of the vertex-amalgamation of two single-rooted graphs (G, t)
and (H,u), when deg(t) = 2 and deg(u) is arbitrarily large. One simply adds up all
terms on the right-hand-sides of Recurrences (2.7) and (2.8) after converting double-
root partials to single-root partials (by ignoring the second root).
• recurrences for the genus distribution of the sequence of open chains of double-
rooted graphs (H,u, v), where deg(v) = 2 and deg(u) can be arbitrarily large, pro-
vided that the genus distribution of (H,u, v) is known and is further analyzed into a
partitioned genus distribution.
It is interesting to note that extending the methods developed in this paper to amalgamating
a single-rooted graph (G, t) with a double-rooted graph (H,u, v), with deg(t) ≥ 3 and
deg(v) ≥ 3, might not be so straight-forward. As illustrated in Example 5.1, the genus-
increment may sometimes be negative (see Research Problem 1 below).
Example 5.1. Figure 10 shows two toroidal imbeddings ι1 : (D3, u) → S1 and ι2 :
(D3, u)→ S1 of the single-rooted dipole (D3, u).
One of the 40 imbeddings of the amalgamated graph X = (D3, u) ∗ (D3, u) that is
consistent with those two imbeddings is also shown in the figure. Note that this is also a
toroidal imbedding, since
V − E + F = 3− 6 + 3 = 0.
136 Ars Math. Contemp. 3 (2010) 121–138
Figure 10: A consistent imbedding of D3 ∗D3 with negative genus-increment.
Thus, the genus-increment in this case is −1.
Research Problem 1. Develop methods for computing the genus distributions when both
amalgamated vertices have abitrarily large degrees. For instance, one might augment the
present approach with other surgical operations, such as splitting a vertex.
Research Problem 2. Develop methods to solve simultaneous recurrences like (3.3), (3.4)
and (4.1), (4.2).
Research Problem 3. As noted in [26], the numbers such as the ones computed in Table 1
and Table 3 appear to support the conjecture that all graphs have unimodal genus distri-
butions. A natural question to ask is whether the vertex-amalgamation of two graphs with
unimodal distributions has a unimodal genus distribution.
Research Problem 4. Results of [26] have been successfully used to compute the genus
distributions of cubic outerplanar graphs ([10]). Can the results of this paper be similarly
used to compute the genus distributions of other non-linear families of graph?
References
[1] L. W. Beineke, R. J. Wilson, J. L. Gross and T. W. Tucker (editors), Topics in Topological
Graph Theory, Cambridge University Press, 2009.
[2] 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.
[3] C. P. Bonnington and C. H. C. Little, The Foundations of Topological Graph Theory, Springer,
1995.
[4] J. Chen, J. L. Gross and R. G. Rieper, Overlap matrices and total imbedding distributions,
Discrete Math. 128 (1994), 73–94.
[5] 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.
[6] M. Conder and P. Dobcsányi, Determination of all regular maps of small genus, J. Combin. The-
ory (B) 81 (2001), 224–242.
[7] 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.
Imran F. Khan et al.: Genus distribution of graph amalgamations: Pasting when. . . 137
[8] L. Goddyn, R. B. Richter, and J. Širáň, Triangular embeddings of complete graphs from grace-
ful labellings of paths, J. Combin. Theory (B) 97 (2007), 964–970.
[9] 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.
[10] J. L. Gross, Genus distributions of cubic outerplanar graphs, preprint, 2010, 23 pages.
[11] J. L. Gross, Genus distribution of graphs under surgery: Adding edges and splitting vertices,
New York J. of Math. 16 (2010), 161-178.
[12] J. L. Gross and M. L. Furst, Hierarchy for imbedding-distribution invariants of a graph,
J. Graph Theory 11 (1987), 205–220.
[13] J. L. Gross, I. F. Khan, and M. I. Poshni, Genus distribution of graph amalgamations: Pasting
at root-vertices, Ars Combinatoria 94 (2010), 33–53.
[14] J. L. Gross, D. P. Robbins and T. W. Tucker, Genus distributions for bouquets of circles, J.
Combin. Theory (B) 47 (1989), 292–306.
[15] J. L. Gross and T. W. Tucker, Topological Graph Theory, Dover, 2001; (original edn. Wiley,
1987).
[16] D. M. Jackson, Counting cycles in permutations by group characters with an application to a
topological problem, Trans. Amer. Math. Soc. 299 (1987), 785–801.
[17] D. M. Jackson and T. I. Visentin, A character-theoretic approach to embeddings of rooted maps
in an orientable surface of given genus, Trans. Amer. Math. Soc. 322 (1990), 343–363.
[18] D. M. Jackson and T. I. Visentin, An Atlas of the Smaller Maps in Orientable and Nonorientable
Surfaces, Chapman & Hall/CRC Press, 2001.
[19] 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.
[20] J. H. Kwak and J. Lee, Genus polynomials of dipoles, Kyungpook Math. J. 33 (1993), 115–125.
[21] J. H. Kwak and J. Lee, Enumeration of graph embeddings, Discrete Math. 135 (1994), 129–
151.
[22] J. H. Kwak and S. H. Shim, Total embedding distributions for bouquets of circles, Discrete
Math. 248 (2002), 93–108.
[23] L. A. McGeoch, Algorithms for two graph problems: computing maximum-genus imbedding
and the two-server problem, PhD thesis, Carnegie-Mellon University, 1987.
[24] B. Mohar and C. Thomassen, Graphs on Surfaces, Johns Hopkins Press, 2001.
[25] B. P. Mull, Enumerating the orientable 2-cell imbeddings of complete bipartite graphs, J. Graph
Theory 30 (1999), 77–90.
[26] M. I. Poshni, I. F. Khan and J. L. Gross, Genus distribution of graphs under edge-
amalgamations, Ars Math. Contemp. 3 (2010) 69–86.
[27] S. Stahl, Region distributions of graph embeddings and Stirling numbers, Discrete Math. 82
(1990), 57–78.
[28] S. Stahl, Permutation-partition pairs III: Embedding distributions of linear families of graphs,
J. Combin. Theory (B) 52 (1991), 191–218.
[29] S. Stahl, Region distributions of some small diameter graphs, Discrete Math. 89 (1991), 281–
299.
[30] E. H. Tesar, Genus distribution of Ringel ladders, Discrete Math. 216 (2000) 235–252.
138 Ars Math. Contemp. 3 (2010) 121–138
[31] T. I. Visentin and S. W. Wieler, On the genus distribution of (p, q, n)-dipoles, Electronic J. of
Combin. 14 (2007), Art. No. R12.
[32] L. X. Wan and Y. P. Liu, Orientable embedding distributions by genus for certain types of
graphs, Ars Combin. 79 (2006), 97–105.
[33] L. X. Wan and Y. P. Liu, Orientable embedding genus distribution for certain types of graphs,
J. Combin. Theory (B) 47 (2008), 19–32.
[34] A. T. White, Graphs of Groups on Surfaces, North-Holland, 2001.