% EJC papers *must* begin with the following two lines. 
\documentclass[12pt]{article}
\usepackage{e-jc}

% Please remove all other commands that change parameters such as
% margins or pagesizes.

% only use standard LaTeX packages
% only include packages that you actually need

% we recommend these ams packages
\usepackage{amsthm,amsmath,amssymb}

\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm} %% E-JC
\usepackage{ifthen,calc}
\usepackage{color}
\usepackage{latexsym}
\usepackage{multicol}
\usepackage[format=hang, margin=10pt]{caption}


% we recommend the graphicx package for importing figures
\usepackage{graphicx}

% use this command to create hyperlinks (optional and recommended)
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

% all overfull boxes must be fixed; 
% i.e. there must be no text protruding into the margins

% declare theorem-like environments

% number theorems, etc in form s.1, s.2, ... 
\newtheorem{thm}{Theorem}[section]
\newtheorem{cor}[thm]{Corollary}
\newtheorem{lemma}[thm]{Lemma} 
\newtheorem{prop}[thm]{Proposition}

\newtheorem{algo}{Algorithm}[section]
\newtheorem{J-com}{JG-comment}[section]

\theoremstyle{definition}
\newtheorem{example}{Example}[section]

\newtheorem{runex}{Running Example -- Part} %[section]

%\newtheorem{conj}{Conjecture}[section]
\newtheorem{rp}{Research Problem}

% number equations and floats in form s.1, s.2, ... 
\numberwithin{equation}{section}
\numberwithin{figure}{section}
\numberwithin{table}{section}



%%%%%%%%%%%%%%%%%%%%     ABBREVIATIONS   %%%%%%%%%%%%%%
\newcommand{\abbr}{\noi\textsc{Abbreviation}. }
\newcommand{\bu}{\bullet}
\newcommand{\comment}{\ni\textsc{Comment}. }
\newcommand{\df}{\noi\textsc{Def}. }\newcommand{\dfs}{\ni\textsc{Definitions}~~}
\newcommand{\Dim}{\textup{dim}}
\newcommand{\Hom}{\textup{Hom}}

\newcommand{\Ker}{\textup{Ker}}
\newcommand{\La}{\Leftarrow}
\newcommand{\llceil}{\left\lceil}
\newcommand{\llfloor}{\left\lfloor}
\newcommand{\lra}{\longrightarrow}
\newcommand{\LRA}{\Leftrightarrow}
\newcommand{\mdef}[1]{\textit{\textbf{#1}}}
\newcommand{\noi}{\noindent}
\newcommand{\nol}{\nolimits}
\newcommand{\notation}{\noi\textsc{Notation}. }
\newcommand{\nsp}{\negthickspace}
\newcommand{\ov}{\overline}
\newcommand{\proofend}[1]{\hfill$\Box$ #1\smallskip}
%\newcommand{\qed}{\qedsymbol}
\newcommand{\ra}{\rightarrow}
\newcommand{\Ra}{\Rightarrow}
\newcommand{\remark}{\noi\textsc{Remark}. }
%\newcommand{\rp}{\noi\textsc{Research~Problem}~~}
\newcommand{\rmand}{\hbox{ and }}
\newcommand{\rrceil}{\right\rceil}
\newcommand{\rrfloor}{\right\rfloor}
\newcommand{\ssm}{\smallsetminus}
\newcommand{\term}{\noi\textsc{Terminology}. }
\newcommand{\un}{\underline}
\newcommand{\und}{^{\rm nd}}
\newcommand{\ust}{^{\rm st}}
\newcommand{\urd}{^{\rm rd}}
\newcommand{\uth}{^{\rm th}}
\newcommand{\vsa}{\vskip-12pt}
\newcommand{\vsb}{\vskip-6pt}


\newcommand{\C}{\mathbb{C}}
\newcommand{\D}{\mathbb{D}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Sy}{\mathbb{S}}
\newcommand{\Z}{\mathbb{Z}}

%%%%%%%%%%%%%%%%%%%%   CUSTOMIZE FONTS   %%%%%%%%%%%%%
\newcommand{\secheadfont}[1]{{\fontsize{16pt}{11pt}\selectfont{#1}}}
\newcommand{\subsecheadfont}[1]{{\fontsize{13pt}{11pt}\selectfont{#1}}}
\newcommand{\titlefont}[1]{{\fontsize{19pt}{11pt}\selectfont{#1}}}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%       PREAMBLE      %%%%%%%%%%%%%%%%


%% TIME STAMP
\newcounter{hours}
\newcounter{minutes}
\newcommand{\printtime}{
	\setcounter{hours}{\time/60}%
	\setcounter{minutes}{\time-\value{hours}*60}
	\ifthenelse{\value{hours}<10}{0}{}\thehours:%
	\ifthenelse{\value{minutes}<10}{0}{}\theminutes}


\parskip4pt  % leave space beween paragraphs

%%%%%%%%%%%%%%%%%% SPECIAL FOR THIS PAPER %%%%%%%%%%%%%%%%%
\newcommand{\f}{$\mathcal F$}
\newcommand{\G}{{\mathcal G}}

\newcommand{\gap}{\hskip-2pt\bu\hskip-2pt}
\newcommand{\ora}{\overrightarrow} 

\newcommand{\subhead}[1]
{\begin{center}
\textsc{#1}
\end{center}}




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}% End of preamble and beginning of text.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\title{{\bf Genus Distributions for Iterated Claws}}

\author{Jonathan L. Gross  \\
\small Department of Computer Science \\
\small Columbia University, New York, NY 10027  \\
\small\tt gross@cs.columbia.edu \\
\and 
 Imran F. Khan \\
\small PUCIT, University of The Punjab \\
\small Lahore 54000, Pakistan \\
\small\tt  imran.farid@pucit.edu.pk \\
\and
Mehvish I. Poshni  \\
\small PUCIT, University of The Punjab \\
\small Lahore 54000, Pakistan \\
\small\tt  mehvish.irfan@pucit.edu.pk    
}

\date{
\dateline{dd mo yr}{dd mo yr} \\
\small Mathematics Subject Classifications: 05C10
}

\maketitle                   % Produces the title.


\begin{abstract}  %\vskip-12pt
We derive a recursion for the genus distributions of the graphs obtained by iteratively attaching a claw to the \hbox{dipole $D_3$}.   The minimum genus of the graphs in this sequence grows arbitrarily large.   The families of graphs whose genus distributions have been calculated previously are either planar or almost planar, or they can be obtained by iterative single-vertex or single-edge amalgamation of small graphs.    A significant simplifying construction within this calculation achieves the effect of an amalgamation at three vertices with a single root vertex, rather than with multiple roots.
\end{abstract} 




\bigskip
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{\large{Introduction}}  % sec1

For $i = 0,1,2, \ldots$, let $g_i(G)$ be the number of distinct cellular embeddings of the graph $G$ in the orientable surface $S_i$ of \hbox{genus $i$}.  The \mdef{genus distribution} of the graph $G$ is the sequence of numbers \par\vsa 
$$g_i(G) : i=0,1, \ldots$$

Let the rooted graph $(Y_0,u_0)$ be isomorphic to the dipole $D_3$, and let the root $u_0$ be either vertex of $D_3$.   For $n=1, 2, \ldots$, we define the \mdef{iterated claw} $(Y_n,u_n)$ to be the graph obtained by subdividing each of the three edges incident on the root vertex $u_{n-1}$ of the iterated claw $(Y_{n-1},u_{n-1})$ and then joining the three new vertices obtained thereby to a new root vertex $u_n$.  Figure \ref{fig:Y3} illustrates the graph $(Y_3,u_3)$.  
\enlargethispage{-12pt}

\begin{figure} [ht]  
\centering   \vskip-9pt
    \includegraphics[width=13cm]{figs-claw/Claw.pdf}  \vskip-6pt
\caption{The rooted graph $(Y_3,u_3)$.}
\label{fig:Y3}
\vskip-3pt
\end{figure}  %\vskip-12pt 
\medskip


\noi The graph $K_{1,3}$ is commonly called a \mdef{claw graph}, which accounts for the name \textit{iterated claw}.  The notation $Y_n$ reflects the fact that a claw graph looks like the letter $Y$.  We observe that $Y_1\cong K_{3,3}$.   We observe also that $Aut(Y_n) = \Z_2\times\D_3$.  In this paper, we derive a recursion for the genus distribution of the iterated claw graphs. 

The \mdef{embeddings} in this paper are cellular and orientable.  We refer to face-boundary walks as \mdef{fb-walks}.  For general background in topological graph theory, see \cite{GrTu87}.  For elaboration on anything mentioned here about treewidth, see \cite{Bo98}.  


\subsection{General context of genus distributions}

The initial focus of topological graph theory was on the minimum genus of a graph, where the crowning achievement was the Ringel-Youngs solution \cite{RiYo68} of the Heawood problem. This  expanded in 1971, to include maximum genus \cite{NSW71}.  Formulating the concept of genus distribution and genus polynomial \cite{GF87} subsequently opened an enumerative branch.  A strategy employed since 1989 in most of the concrete calculations of genus distributions is the \textit{partitioning of genus distributions}  \cite{FGS89}, which leads to simultaneous recursions.   

After proofs of log-concavity \cite{FGS89, GRT89} were derived for several infinite families of graphs (with rising maximum genus), it was conjectured \cite{GRT89} that all genus distributions are log-concave.  Stahl \cite{Stah97}  successfully used real-rootedness to show that various genus distributions are log-concave.  Although the present paper does not address this issue, it has been recently proved \cite{GMTW13b} that the genus polynomials of iterated claws are real-rooted.   

Stahl \cite{Stah91} has characterized graph sequences that can be derived by some kinds of repetitive topological operations as \textit{linear}, and he calculated genus distributions for a number of linear families.  A recent paper \cite{GMTW13a} proves the log-concavity of some of Stahl's linear families and also of many others.   In recent years, genus distributions have been calculated for cubic outerplanar graphs \cite{Gr11b}, quartic outerplanar graphs \cite{PKG11}, and cubic Halin graphs \cite{Gr13}, none of which are linear families.  Log-concavity has most recently been proved \cite{GMTW13c} for \textit{Ringel ladders}, the first infinite non-linear family of rising maximum genus for which log-concavity has been established.  

Stahl's representation \cite{Stah91} of a partitioned genus distribution by a vector of polynomials (which we call a \textit{pgd-vector}) and of the effect of a topological operation on the pgd-vector by a matrix (which we call a \textit{production matrix}) is adopted in this paper.  It will be seen in a subsequent paper on iterated claws \cite{GMTW13b} how this algebraic representation enables us to use generating functions not only to derive an explicit formula for the genus polynomials of iterated claws from the recursions we derive herein, but also to prove the real-rootedness of these genus polynomials, which implies their log-concavity.  


\subsection{Context of the genus distribution of iterated claws}

It is easy enough to demonstrate that each of the iterated claws $Y_n$ has treewidth 3, by the direct construction of a decomposition tree.  The 3-regular Halin graphs \cite{Gr13} and the rectangular mesh graphs of the form $P_3\Box P_n$ \cite{KPG12}, where $P_k$ is the $k$-vertex path (and the square box $\Box$ denotes cartesian product), are families of graphs of treewidth 3 for which genus distribution algorithms were previously derived.  Since the \hbox{graph $Y_{3n}$} contains $n$ disjoint copies of $K_{3,3}$, it follows that the minimum genus \hbox{of $Y_{3n}$} is at least $n$.  Whereas Halin graphs and rectangular mesh graphs are planar, the minimum genus of the graphs in the sequence $Y_1, Y_2, \ldots$ grows arbitrarily large and is nondecreasing.  
 
The intricacy of practical methods needed for calculating genus distributions appears to rise steadily with rising treewidth.   This descriptive complexity (i.e., in the sense of Kolmogorov \cite{Ko65} and Chaitin \cite{Ch66}) is also reflected in the construction given in \cite{Gr12} for an algorithm for genus distribution of graphs of any fixed treewidth and fixed maximum degree, which despite being a quadratic-time algorithm, is far from practical.  In particular, the constant factor in the time for the algorithm rises exponentially not only with the degrees of the roots, but also with the number of roots, which in turn rises proportionally with rising treewidth. 

An innovative feature of this calculation is that although the graphs to which it is applied are of treewidth 3, only one root is needed.  Although the derivation requires considerable attention to details, the genus distribution calculation method obtained thereby involves only three \textit{productions}, and it can be applied rather easily with the aid of a spreadsheet. 




\medskip
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{\large{Partials and Production Matrices} \label{sec:prod}}  % sec2

Development of partitioned genus distributions and productions began with \cite{GKP10} and continued in \cite{Gr11a,PKG10,KPG10}.  They are used in numerous genus distribution calculations, for instance, of 3-regular outerplanar graphs \cite{Gr11b}, of 4-regular outerplanar graphs \cite{PKG11}, of 3-regular Halin graphs \cite{Gr13}, and of 3-regular series-parallel graphs \cite{GrKo12}.   We confine the discussion here to what is needed for the genus distributions of iterated claws. 

\enlargethispage{12pt}

For each iterated claw $(Y_n,u_n)$ we define the following three \mdef{partial genus distributions}, also called \mdef{partials}. 
\begin{eqnarray*}
\noalign{\vskip-3pt}
a_{n,i} &=& \text{the number of embeddings $Y_n\to S_i$ such that} \\[-3pt]
	&& \text{three different fb-walks are incident on the root $u_n$;} \\
b_{n,i} &=& \text{the number of embeddings $Y_n\to S_i$ such that exactly} \\[-3pt]
	&& \text{two different fb-walks are incident on the root $u_n$;}\\
c_{n,i} &=& \text{the number of embeddings $Y_n\to S_i$ such that} \\[-3pt]
	&& \text{one fb-walk is incident three times on the root $u_n$.}
\end{eqnarray*} 
We will be representing each partial genus distribution by a polynomial.  We define the generating functions 
\begin{align*}
\noalign{\vsb}
A_n(x) &\,=\, \sum_{i=0}^\infty a_{n,i}x^i \\
B_n(x) &\,= \,\sum_{i=0}^\infty b_{n,i}x^i \\
C_n(x) &\,=\,\sum_{i=0}^\infty c_{n,i}x^i  
\end{align*} 

Clearly, the full genus distribution is the sum of the partials.  That is, for $i\,=\,0,1,2, \ldots$, we define
\begin{align*} 
g_{n,i} &\,=\,  a_{n,i}\,+\,b_{n,i}\,+\,c_{n,i} \\
\noalign{\noi and the \mdef{genus polynomial}}
G_n(x) &\,=\,  A_n(x) \,+\, B_n(x) \,+\, C_n(x)   
\end{align*}
In general, a listing of the non-zero values of all the partials for every genus $i$ is called a \mdef{partitioned genus distribution} (sometimes abbreviated \mdef{pgd}).  

As indicated by \cite{Gr12}, the number of partials needed for a genus distribution calculation tends to grow exponentially with the number of roots.   In previous papers, the number of roots used for the calculations of genus distributions of recursively specified graph sequences has tended to be one more than the number of vertices (or edges) at which a graph is attached to an additional graph fragment in the recursion step.  Here we need only one root, even though there are three vertices of attachment. 
\medskip


\subsection{Pgd-vectors and production matrices}  

We observe, by direct construction of the embeddings from the rotation systems,  that the graph $(Y_0,u_0)$ has the following partitioned genus distribution:
\begin{equation}
a_{0,0} = 2 \quad c_{0,1}=2 
\end{equation} \label{pgd:Y0} 
In general, a \mdef{pgd-vector} is a vector with a component for each partial genus distribution, whose value is the partial genus polynomial for that partial.  Thus, we can represent the pgd \eqref{pgd:Y0}  by the pgd-vector 
$$\ora{(Y_0,u_0)} \,=\; \left[A_0(x),\, B_0(x),\, C_0(x) \right]  \,=\; \left[2,0,2x \right] $$
(or by its transpose). This pgd-vector  for $(Y_0,u_0)$ will serve as the base case for a recursion that yields the genus distribution of every iterated claw graph $Y_n$.  To look ahead a bit, we will derive a $3\times3$ \mdef{production matrix}  
\begin{equation}  \label{matrix M}
 M \,=\, \left[ \begin{matrix}
0 & 2 & 8 \\
12x & 12x & 0 \\
~4x^2 & 2x & 8x 
\end{matrix} \right] 
\end{equation}
and prove Corollary \ref{cor:matmult} that 
\begin{equation}\label{eq:mat}
\ora{(Y_n,u_n)}^T =  M^n \ora{(Y_0,u_0)}^T,
\end{equation} 
where the superscript $T$ indicates the transpose of a matrix.   The reason for the name \textit{production matrix} becomes clear in Section \ref{sec:recursion}. 

Corollary \ref{cor:matmult} is equivalent to this system of recurrences 
\begin{alignat}{7}
&a_{n,i} \;=\; &&\phantom{\;+\;}\hskip10pt  2b_{n-1,i}   &&\;+ ~~8c_{n-1,i} \notag \\
&b_{n,i} \;=\; 12a_{n-1,i-1} &&\;+\; 12b_{n-1,i-1} \;&& \label{rec:simult} \\
&c_{n,i} \;=\;  \hskip6pt 4a_{n-1,i-2} &&\;+\;  \hskip5pt 2b_{n-1,i-1}  &&\;+ ~~8c_{n-1,i-1} \notag
\end{alignat} 
or to this system of simultaneous generating functions: 
\begin{alignat}{7}
&A_n(x) \;=\; &&\phantom{\;+\;}\hskip17pt  2B_{n-1}(x)   &&\;+\; \hskip7pt 8C_{n-1}(x) \notag \\
&B_n(x) \;=\; 12xA_{n-1}(x) &&\;+\; 12xB_{n-1}(x) \;&& \label{rec:GF} \\
&C_n(x) \;=\;  \hskip6pt 4x^2A_{n-1}(x) &&\;+\;  \hskip5pt 2xB_{n-1}(x)  &&\;+\; 8xC_{n-1}(x)  \notag
\end{alignat} 

In a recent paper \cite{GMTW13b}, an explicit formula for the genus polynomial $G_n(x)$ is derived from  Equation \eqref{eq:mat} with the aid of generating functions.  Moreover, it is proved that these genus polynomials are real-rooted, which implies that they are log-concave.  



\medskip
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{\large{Root-Rotation Reversal Lemmas} \label{sec:lemmas}}  % sec3

In Section \ref{sec:prod}, we defined the three partial genus distributions $a_{n,i}$,  $b_{n,i}$,  and $c_{n,i}$.  We associate to them \mdef{embedding types}, called $a_i$, $b_i$, and $c_i$, respectively. For instance, a type-$a_i$ embedding is an embedding of any iterated claw in the surface $S_i$ such that three different fb-walks are incident on the root.   As we shall soon see, one of the three types splits into two subtypes.  

Accordingly, if we were to separately analyze each of the 16 possible embeddings that can result from adding a claw to an embedding of $(Y_{n-1},u_{n-1})$, for each of the four possible types (or subtypes) of partials at the root $u_{n-1}$, there would be 64 cases to consider.  By applying the three lemmas of this section, we can reduce the work needed for each of the three types of embeddings to half as many cases.  Our objective in this section and Section \ref{sec:recursion} is to derive Equation \eqref{eq:mat}. 
\smallskip

Embedding a graph $G$ in a surface partitions the oriented edges of $G$ into fb-walks.  Changing the rotation at any vertex of an embedded graph changes the fb-walks.  A topologically intuitive perspective on a change of rotation at a vertex $u$ is that each fb-walk incident at $u$ is cut at each such incidence.  The resulting subwalks are called \mdef{strands}. The effect on the set of fb-walks of changing the rotation is that these strands are recombined into fb-walks and the number of corners at $u$ is once again the degree of $u$.  The number of resulting fb-walks may be larger or smaller than the previous number, depending on the particulars of the change of rotation.  (In an orientable embedding, the parity of the number of fb-walks is preserved.) The genus of the embedding surface rises, stays the same, or falls, depending on the new number of fb-walks and its relation to the old number. 

We now observe that the type-$c_i$ embeddings of a rooted graph $(G,u)$ with trivalent root $u$ can be partitioned into two subtypes, which are called \mdef{subtype $c_i'$} and \mdef{subtype $c_i''$}.  Suppose that the single oriented fb-walk $W$ incident at $u$ is cut at each corner, so that there are three oriented strands.  The head of each of the three strands meets the tail of some other strand.  Of course, the head and tail of each strand are at the vertex $u$.  As illustrated in Figure \ref{fig:subtype} (right), in the subtype~$c_i''$, the last oriented edge (at the head) of each of the three strands is the reverse of the first oriented edge of that strand.  Subtype $c_i'$ is the alternative possible assembly of the strands into a single cycle.  
\smallskip

\remark All embedding surfaces depicted here are taken to have counter-clockwise orientation. 
\smallskip

\begin{figure} [ht]  
\centering   \vskip-3pt
    \includegraphics[width=9cm]{figs-claw/subtype.pdf}  \vskip-3pt
\caption{Embedding subtypes $c_i'$ and $c_i''$.}
\label{fig:subtype}
\vskip-3pt
\end{figure}  %\vskip-12pt 


\begin{lemma} \label{lemma:a}
Let a rooted graph $(G,u)$ with a 3-valent root be embedded in the surface $S_i$ so that there are three distinct fb-walks incident on root $u$, that is, an embedding of type $a_i$.  Then the result of reversing the rotation at root $u$ is an embedding in the surface $S_{i+1}$ of type $c_{i+1}'$.  
\end{lemma}

\begin{proof} \vskip-6pt
Lemma \ref{lemma:a} follows from the face-tracing in Figure \ref{fig:a0-c1}.
\end{proof}
\smallskip

\begin{figure} [ht]  
\centering   \vskip-9pt
    \includegraphics[width=10cm]{figs-claw/a0->c1.pdf}  \vskip-3pt
\caption{Reversing the rotation at a 3-valent root of type $a_i$.}
\label{fig:a0-c1}
\vskip-3pt
\end{figure}  %\vskip-12pt 

\enlargethispage{12pt}

\begin{lemma} \label{lemma:b}
Let a rooted graph $(G,u)$ with a 3-valent root be embedded in the surface $S_i$ so that there are exactly two distinct fb-walks incident on root $u$, that is, an embedding of type $b_i$.  Then the result of reversing the rotation at root $u$ is another embedding of type~$b_i$.  
\end{lemma}

\begin{proof} \vskip-6pt
Lemma \ref{lemma:b} follows from the face-tracing in Figure \ref{fig:b0-b0}.  
\end{proof}
\smallskip

\begin{figure} [ht]  
\centering   \vskip-9pt
    \includegraphics[width=10cm]{figs-claw/b0->b0.pdf}  \vskip-3pt
\caption{Reversing the rotation at a 3-valent root of type $b_i$.}
\label{fig:b0-b0}
\vskip-3pt
\end{figure}  %\vskip-12pt 




\begin{lemma}  \label{lemma:c}
Let a rooted graph $(G,u)$ with a 3-valent root be embedded in the surface $S_i$ so that there is only one fb-walk incident on root $u$.  If this embedding is subtype $c_i'$, then the result of reversing the rotation at root $u$ is an embedding of type $a_{i-1}$.  If subtype $c_i''$, then the result of reversing the rotation at root $u$ is another embedding of type $c_i''$.  
\end{lemma}

\begin{proof} \vskip-6pt
We observe in Lemma \ref{lemma:a} that reversing the rotation of the root of a graph embedding of type $a_i$ yields an embedding of subtype $c_{i+1}'$.  It follows that reversing the rotation of the root of a graph embedding of subtype $c_i'$ yields an embedding of type $a_{i-1}$. The subtype $c_i''$-part of Lemma \ref{lemma:c} follows from the face-tracing in  Figure \ref{fig:c''}. \end{proof}

\begin{figure} [ht]  
\centering   \vskip-9pt
    \includegraphics[width=9cm]{figs-claw/c''.pdf}  \vskip-3pt
\caption{Reversing an embedding of subtype $c_i''$.}
\label{fig:c''}
\vskip-3pt
\end{figure}  %\vskip-12pt 




\bigskip
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{\large{Derivation of the Productions} \label{sec:recursion}}  % sec4

In this section, we prove four propositions to derive the four productions that enable us to calculate the genus distribution of any iterated claw.   It turns out that the last two productions can be combined.  We then summarize these propositions by the main result of this paper.  

Although we give enough information to combinatorially verify all of our assertions here about the types of embeddings that result from  claw extensions of a given embedding, or from reversals of rotation at a trivalent vertex, we find it much easier to follow fb-walks in diagrams, than to represent the equivalent combinatorial face-tracing by mathematical prose.   Moreover, we find that errors are less likely to occur when assertions about fb-walks are justified by diagrams.  Furthermore, the diagrams of local configurations within an embedding are frequently intuitively suggestive of additional properties of the embeddings they represent. 
\smallskip

\enlargethispage{6pt}
\begin{prop} \label{prop:a} 
Let $\iota\!:\!(Y_{n-1},u_{n-1})\to S_i$ be an embedding of \hbox{type $a_i$} of an iterated claw. Then of the 16 possible embeddings of $(Y_n,u_n)$ whose rotations are consistent with those of $Y_{n-1}$, there are 12 embeddings of type $b_{i+1}$ and 4 of subtype $c_{i+2}''$.
\end{prop} 

\begin{proof} \vskip-6pt
Figure \ref{fig:a-init} illustrates an embedding of type $a_i$ of the iterated claw $(Y_{n-1},u_{n-1})$ and an extension to an embedding of the iterated claw $(Y_n,u_n)$.  In this designated initial extension, the rotations at the four new vertices are as in Table \ref{tbl:clawrots}:  

\begin{table}[h!]   
\caption{A set of rotations for the vertices of the new claw.}
\begin{eqnarray*}
\noalign{\vskip-12pt}
u_n. && x_{n-1}~z_{n-1}~y_{n-1} \\[-2pt]
x_{n-1}. && u_{n-1}~u_{n}~x_{n-2} \\[-2pt]
y_{n-1}. && u_{n-1}~u_{n}~y_{n-2} \\[-2pt]
z_{n-1}. && u_{n}~u_{n-1}~z_{n-2} 
\end{eqnarray*}
\label{tbl:clawrots}
\end{table}
%\smallskip

\begin{figure} [ht]  
\centering   \vskip-24pt
    \includegraphics[width=12.5cm]{figs-claw/a-init.pdf}  \vskip-6pt
\caption{An initial embedding of type $b_{i+1}$ obtained by adding a claw to an embedding of subtype $a_i$.}
\label{fig:a-init}
\vskip-3pt
\end{figure}  %\vskip-12pt 


\noi We have increased the number of vertices by four and the number of edges by six.  The number of faces is unchanged.  Accordingly, the genus of the resulting embedding surface is $i+1$.  The number of fb-walks incident at the new root vertex $u_n$ is two.  Thus, this particular set of rotations at the four new vertices yields an embedding of \hbox{type $b_{i+1}$}.   According to Lemma \ref{lemma:b}, when we reverse the rotation at the root $u_n$, the resulting embedding will still be of type $b_{i+1}$.  In what follows, we reverse the rotations at each non-empty subsets of the vertices $x_{n-1}, y_{n-1}, z_{n-1}$, without and with the reversal of rotation at $u_n$, and thereby obtain the types of the other 14 embeddings of $Y_n$ that are consistent with the given embedding of $Y_{n-1}$.  
\smallskip


In Figure \ref{fig:a-x,y}, the rotations at vertex $x_{n-1}$ (left) and at $y_{n-1}$ (right), respectively, are reversed.  We observe in the drawing (or by combinatorial face-tracing) that the numbers of vertices, edges, and faces are the same as the drawing after the arrow in Figure \ref{fig:a-init}.  In both drawings, there are exactly two fb-walks incident at the root vertex $u_n$.  Accordingly, both embeddings are of type $b_{i+1}$.  Moreover, by Lemma \ref{lemma:b}, when the rotation at root vertex $u_n$ is reversed in either embedding, the resulting embedding is also of type $b_{i+1}$. 



\begin{figure} [ht]  
\centering   \vskip-9pt
    \includegraphics[width=13cm]{figs-claw/a-x,y.pdf}  \vskip-6pt
\caption{Rotation reversals at vertex $x_{n-1}$ (left) and at vertex $y_{n-1}$ (right) yield embeddings of type $b_{i+1}$.}
\label{fig:a-x,y}
\vskip-3pt
\end{figure}  %\vskip-12pt 

%\eject

Figures \ref{fig:a-z,xy}, \ref{fig:a-xz,yz}, and \ref{fig:a-xyz} represent the five other extensions of the given embedding of $(Y_{n-1},u_{n-1})$ of type $a_i$ that can be obtained by reversing rotations at the five remaining choices of subsets of new vertices $x_{n-1}$, $y_{n-1}$, and $z_{n-1}$ of the iterated claw $(Y_n, u_n)$.  

\enlargethispage{12pt}

\begin{figure} [h!]  
\centering   \vskip-9pt
    \includegraphics[width=13cm]{figs-claw/a-z,xy.pdf}  \vskip-6pt
\caption{Rotation reversal at vertex $z_{n-1}$ (left) yields an embedding of type $c_{i+2}''$, and reversals at vertices $x_{n-1}$ and $y_{n-1}$ (right) also yield type $c_{i+2}''$.}
\label{fig:a-z,xy}
\end{figure}  %\vskip-12pt 

In Figure \ref{fig:a-z,xy} (left), the rotation at vertex $z_{n-1}$ is reversed.  The number of faces is two fewer than in Figure \ref{fig:a-init}, and exactly one fb-walk is incident three times at the root vertex $u_n$.  Accordingly, the embedding is of type $c_{i+2}$.  By face-tracing, we see that it is of \hbox{subtype $c_{i+2}''$}.  By Lemma \ref{lemma:c}, reversing the rotation at root vertex $u_n$ also yields an embedding of subtype $c_{i+2}''$.   A similar analysis applies to \hbox{Figure \ref{fig:a-z,xy}} (right), in which the rotations at vertices $x_{n-1}$ and $y_{n-1}$ have been reversed.  Thus, the tally so far is six embeddings of type $b_{i+1}$ and four of subtype $c_{i+2}''$. 


In Figure \ref{fig:a-xz,yz} (left), the rotation reversals are at vertices $x_{n-1}$ and $z_{n-1}$.  The number of faces is the same as in Figure \ref{fig:a-init}, and there are two fb-walks at the root vertex $u_n$.  Accordingly, the embedding is of type $b_{i+1}$.  By Lemma \ref{lemma:b}, reversing the rotation at root vertex $u_n$ also yields an embedding of type $b_{i+1}$.   A similar analysis applies to \hbox{Figure \ref{fig:a-xz,yz}} (right), in which the rotations at vertices $y_{n-1}$ and $z_{n-1}$ have been reversed.   
\smallskip

\begin{figure} [ht]  
\centering   \vskip-9pt
    \includegraphics[width=13cm]{figs-claw/a-xz,yz.pdf}  \vskip-6pt
\caption{Rotation reversals at vertices $x_{n-1}$ and $z_{n-1}$ (left) yield type $b_{i+1}$, and reversals at $y_{n-1}$ and $z_{n-1}$ (right) also yield embeddings of type $b_{i+1}$.}
\label{fig:a-xz,yz}
\vskip-3pt
\end{figure}  %\vskip-12pt 


In Figure \ref{fig:a-xyz}, the rotations at vertices $x_{n-1}$, $y_{n-1}$, and $z_{n-1}$ are reversed.  The number of faces is the same as in Figure \ref{fig:a-init}, and there are two fb-walks at the root vertex $u_n$.  Accordingly, the embedding is once again of type $b_{i+1}$.  By Lemma \ref{lemma:b}, reversing the rotation at root vertex $u_n$ also yields an embedding of type $b_{i+1}$.   
\smallskip

\begin{figure} [ht]  
\centering   %\vskip-9pt
    \includegraphics[width=6cm]{figs-claw/a-xyz.pdf}  \vskip-6pt
\caption{Rotation reversals at the three vertices $x_{n-1}$, $y_{n-1}$, and $z_{n-1}$ yield an embedding of type $b_{i+1}$.}
\label{fig:a-xyz}
\vskip-3pt
\end{figure}  %\vskip-12pt 

%\eject  %%%

The \textit{production} \vskip-24pt
\begin{equation} \label{prod:a} 
a_i ~\lra~ 12b_{i+1}+4c_{i+2}'' 
\end{equation} 
summarizes the results we have just now derived. 
\end{proof}
\smallskip

In general, a \mdef{production} is an algebraic expression of the effects on the partial genus distribution of a graph topological operation according to its action on an embedding of that graph.  For instance, Production \eqref{prod:a} represents the effect on the pgd of the claw-extension operation on a type-$a_i$ embedding, so $a_i$ appears at the tail of the arrow, and it is called the \mdef{antecedent} of the production.  As we discussed within the proof of Proposition \ref{prop:a}, among the 16 embeddings obtainable by adding a claw to a type-$a$ embedding, there are 12 of type $b_{i+1}$ and 4 of subtype $c''_{i+2}$.  The expression $12b_{i+1}+4c''_{i+2}$ that appears at the head of the arrow is called the \mdef{consequent} of the production. 
\smallskip




\begin{prop} \label{prop:b}
Let $\iota\!:\!(Y_{n-1},u_{n-1})\to S_i$ be an embedding of \hbox{type $b_i$} of an iterated claw. Then of the 16 possible embeddings of $(Y_n,u_n)$ whose rotations are consistent with those of $Y_{n-1}$, there are 2 embeddings of \hbox{type $a_i$}, 12 of type $b_{i+1}$ and 2 of type $c_{i+1}'$.
\end{prop} 

\begin{proof}\vskip-3pt

Figure \ref{fig:b-init} (left) illustrates an embedding of type $b_i$ of the iterated claw $(Y_{n-1},u_{n-1})$ and (right) an extension to an embedding of the iterated claw $(Y_n,u_n)$.  In the designated initial extension of this embedding, the rotations at the four new vertices are again as in \hbox{Table \ref{tbl:clawrots}}.
\smallskip

\begin{figure} [ht]   % fig4.6
\centering   \vskip-9pt
    \includegraphics[width=12.5cm]{figs-claw/b-init.pdf}  \vskip-6pt
\caption{An initial embedding of type $b_{i+1}$ obtained by adding a claw to an embedding of subtype $b_i$.}
\label{fig:b-init}
\vskip-3pt
\end{figure}  %\vskip-12pt 

\noi Reasoning as in the proof of Proposition \ref{prop:a}, we see that this particular set of rotations at the four new vertices yields an embedding of type $b_{i+1}$.   According to Lemma \ref{lemma:b}, when we reverse the rotation at the root $u_n$, the resulting embedding will still be of type $b_{i+1}$.  

We continue as in Proposition \ref{prop:a}.  In Figure \ref{fig:b-x,y}, the rotations at vertex $x_{n-1}$ (left) and at $y_{n-1}$ (right), respectively, are reversed.  In both drawings, there are exactly two fb-walks incident at the root vertex $u_n$.  Accordingly, both embeddings are of type $b_{i+1}$.  Moreover, by Lemma \ref{lemma:b}, when the rotation at root vertex $u_n$ is reversed in either embedding, the resulting embedding is also of type $b_{i+1}$. 


\begin{figure} [ht]   % fig4.7
\centering   \vskip-9pt
    \includegraphics[width=13cm]{figs-claw/b-x,y.pdf}  \vskip-6pt
\caption{Rotation reversals at vertex $x_{n-1}$ (left) and at vertex $y_{n-1}$ (right) yield embeddings of type $b_{i+1}$.}
\label{fig:b-x,y}
\vskip-3pt
\end{figure}  %\vskip-12pt 


In Figure \ref{fig:b-z,xy} (left), the rotation at vertex $z_{n-1}$ is reversed.  Once again, the embedding is of type $b_{i+1}$.   By Lemma \ref{lemma:b}, reversing the rotation at root vertex $u_n$ yields another embedding of type $b_{i+1}$.  A similar analysis applies to \hbox{Figure \ref{fig:b-z,xy}} (right), in which the rotations at vertices $x_{n-1}$ and $y_{n-1}$ have been reversed.  Thus, the tally so far is ten embeddings of type $b_{i+1}$.  


\begin{figure} [ht]  % fig 4.8
\centering   \vskip-9pt
    \includegraphics[width=13cm]{figs-claw/b-z,xy.pdf}  \vskip-6pt
\caption{Rotation reversal at vertex $z_{n-1}$ (left) yields an embedding of type $b_{i+1}$, and reversals at vertices $x_{n-1}$ and $y_{n-1}$ (right) also yield type $b_{i+1}$.}
\label{fig:b-z,xy}
\vskip-3pt
\end{figure}  %\vskip-12pt 


In Figure \ref{fig:b-xz,yz} (left), the rotation at vertices $x_{n-1}$ and $z_{n-1}$ are reversed.  The embedding is of type $b_{i+1}$.  By Lemma \ref{lemma:b}, reversing the rotation at root vertex $u_n$ also yields an embedding of type $b_{i+1}$.   When the rotations at vertices $y_{n-1}$ and $z_{n-1}$ have been reversed, as in \hbox{Figure \ref{fig:b-xz,yz}} (right), the resulting embedding is of type $c_{i+1}'$.  Reversing the rotation at root vertex $u_n$ now yields an embedding of type $a_{i}$, by Lemma \ref{lemma:c}.   

\enlargethispage{12pt}


\begin{figure} [h!t]  % fig4.9
\centering   \vskip-9pt
    \includegraphics[width=13cm]{figs-claw/b-xz,yz.pdf}  \vskip-6pt
\caption{Rotation reversals at vertices $x_{n-1}$ and $z_{n-1}$ (left) yield type $b_{i+1}$, and reversals at $y_{n-1}$ and $z_{n-1}$ (right) yield an embedding of type $c_{i+1}'$.}
\label{fig:b-xz,yz}
\end{figure}  %\vskip-12pt 
\smallskip

\eject

In Figure \ref{fig:b-xyz}, the rotation at the three vertices $x_{n-1}$, $y_{n-1}$, and $z_{n-1}$ are reversed.  The embedding is of type $c_{i+1}'$.  By Lemma \ref{lemma:c}, reversing the rotation at root vertex $u_n$ now yields an embedding of type $a_{i}$.   
\smallskip

\begin{figure} [ht]  
\centering   %\vskip-9pt
    \includegraphics[width=6cm]{figs-claw/b-xyz.pdf}  \vskip-6pt
\caption{Rotation reversals at the three vertices $x_{n-1}$, $y_{n-1}$, and $z_{n-1}$ yield an embedding of type $c_{i+1}'$.}
\label{fig:b-xyz}
\vskip-3pt
\end{figure}  %\vskip-12pt 
\medskip


The production 
\begin{equation} \label{prod:b} 
b_i ~\lra~ 2a_i + 12b_{i+1} + 2c_{i+1}' 
\end{equation} 
summarizes the results we have considered in this second proposition.
\end{proof}
\medskip


\begin{prop} \label{prop:c'}
Let $\iota\!:\!(Y_{n-1},u_{n-1})\to S_i$ be an embedding of \hbox{subtype $c_i'$} of an iterated claw. Then of the 16 possible embeddings of $(Y_n,u_n)$ whose rotations are consistent with those of $Y_{n-1}$, there are 8 embeddings of type $a_i$ and 8 of type $c_{i+1}'$.
\end{prop} 

\enlargethispage{6pt}


\begin{proof}\vskip-12pt
Figure \ref{fig:c'-init} (left) shows a  subtype-$c_i'$ embedding of the iterated claw $(Y_{n-1},u_{n-1})$ and (right) an extension to an embedding of $(Y_n,u_n)$.  In the designated initial extension of this embedding, the rotations at the four new vertices are yet again as in Table~\ref{tbl:clawrots}.  


\begin{figure} [h!]  
\centering   \vskip-12pt
    \includegraphics[width=12.5cm]{figs-claw/c'-init.pdf}  \vskip-3pt
\caption{An initial embedding of type $c_{i+1}'$ obtained by adding a claw to an embedding of subtype $c_i'$.}
\label{fig:c'-init}
\vskip-3pt
\end{figure}  %\vskip-12pt 
\medskip

\noi We see that this particular set of rotations at the four new vertices yields an embedding of type $c_{i+1}'$.   According to Lemma \ref{lemma:c}, when we reverse the rotation at the root $u_n$, the resulting embedding will be of type $a_{i}$.  

In Figure \ref{fig:c-x,y}, the rotations at vertex $x_{n-1}$ (left) and at $y_{n-1}$ (right), respectively, are reversed.  Both embeddings are of type $c_{i+1}'$.  By Lemma \ref{lemma:c}, when the rotation at root vertex $u_n$ is reversed in either embedding, the resulting embedding is of type $a_{i}$. 


\begin{figure} [ht]  % fig4.12 
\centering   %\vskip-9pt
    \includegraphics[width=13cm]{figs-claw/c'-x,y.pdf}  \vskip-3pt
\caption{Rotation reversals at vertex $x_{n-1}$ (left) and at vertex $y_{n-1}$ (right) yield embeddings of type $c'_{i+1}$.}
\label{fig:c-x,y}
\vskip-3pt
\end{figure}  %\vskip-12pt 
\medskip


In Figure \ref{fig:c-z,xy} (left), the rotation at vertex $z_{n-1}$ is reversed.  The embedding is of type $a_{i}$.   By Lemma \ref{lemma:a}, reversing the rotation at root vertex $u_n$ yields an embedding of type $c_{i+1}'$.  A similar analysis applies to \hbox{Figure \ref{fig:c-z,xy}} (right), in which the rotations at vertices $x_{n-1}$ and $y_{n-1}$ have been reversed.  Thus, the tally so far is five embeddings of type $a_{i}$ and five of type $c_{i+1}'$.  


\begin{figure} [ht]  % fig4.13
\centering   \vskip-9pt
    \includegraphics[width=13cm]{figs-claw/c'-z,xy.pdf}  \vskip-6pt
\caption{Rotation reversal at vertex $z_{n-1}$ (left) yields an embedding of type $a_{i}   $, and reversals at vertices $x_{n-1}$ and $y_{n-1}$ (right) also yield type $a_i$.}
\label{fig:c-z,xy}
\vskip-3pt
\end{figure}  %\vskip-12pt 
\medskip



In Figure \ref{fig:c'-xz,yz} (left), the rotation at vertices $x_{n-1}$ and $z_{n-1}$ are reversed.  The embedding is of type $c_{i+1}'$.  By Lemma \ref{lemma:c}, reversing the rotation at root vertex $u_n$ yields an embedding of type $a_{i}$.   When the rotations at vertices $y_{n-1}$ and $z_{n-1}$ have been reversed, as in \hbox{Figure \ref{fig:c'-xz,yz}} (right), the resulting embedding is again of type $c_{i+1}'$.  By Lemma \ref{lemma:c}, reversing the rotation at root vertex $u_n$ again yields an embedding of type $a_{i}$. 
\medskip


\begin{figure} [ht]  % fig 4.14
\centering   \vskip-9pt
    \includegraphics[width=13cm]{figs-claw/c'-xz,yz.pdf}  \vskip-6pt
\caption{Rotation reversals at vertices $x_{n-1}$ and $z_{n-1}$ (left) yield type $c_{i+1}'$, as do reversals at $y_{n-1}$ and $z_{n-1}$ (right).}
\label{fig:c'-xz,yz}
\vskip-3pt
\end{figure}  %\vskip-12pt 
\medskip

\eject

In Figure \ref{fig:c'-xyz}, the rotation at the three vertices $x_{n-1}$, $y_{n-1}$, and $z_{n-1}$ are reversed.  The embedding is of type $c_{i+1}'$.  By Lemma \ref{lemma:c}, reversing the rotation at root vertex $u_n$ now yields an embedding of type $a_{i}$.   
\smallskip

\begin{figure} [ht]  
\centering   \vskip-9pt
    \includegraphics[width=6cm]{figs-claw/c'-xyz.pdf}  \vskip-6pt
\caption{Rotation reversals at the three vertices $x_{n-1}$, $y_{n-1}$, and $z_{n-1}$ yield an embedding of type $c_{i+1}'$.}
\label{fig:c'-xyz}
\vskip-3pt
\end{figure}  %\vskip-12pt 


The production  \vskip-18pt
\begin{equation}
c_i' ~\lra~ 8a_i + 8c_{i+1}'  \label{prod:c'}
\end{equation}
summarizes the results we have considered in this third proposition.
\end{proof} 
\smallskip


\begin{prop} \label{prop:c''}
Let $\iota\!:\!(Y_{n-1},u_{n-1})\to S_i$ be a  \hbox{subtype $c_i''$}-embedding of an iterated claw. Then of the 16 possible embeddings of $(Y_n,u_n)$ whose rotations are consistent with those of $Y_{n-1}$ at every vertex except for the four on the newly attached claw, there are 8 embeddings of \hbox{type $a_i$} and 8 of type $c_{i+1}'$.
\end{prop} 

\begin{proof}\vskip-3pt
Figure \ref{fig:c''-init} illustrates an extension of a subtype-$c_i'$ embedding of the iterated claw $(Y_{n-1},u_{n-1})$ to an embedding of $(Y_n,u_n)$.  In the designated initial extension of this embedding, the rotations at the four new vertices are, as usual, as in Table \ref{tbl:clawrots}.


\begin{figure} [ht]  
\centering   \vskip-9pt
    \includegraphics[width=10.5cm]{figs-claw/c''-init.pdf}  \vskip-6pt
\caption{An initial embedding of subtype $c_{i+1}'$ obtained by adding a claw to an embedding of subtype $c_i''$.}
\label{fig:c''-init}
\vskip-3pt
\end{figure}  %\vskip-12pt 
\medskip


\noi We see that this particular set of rotations at the four new vertices yields a type-$c_{i+1}'$ embedding.   By Lemma \ref{lemma:c}, when we reverse the rotation at the root $u_n$, the resulting embedding will be of type $a_{i}$.  

In Figure \ref{fig:c''-x,y}, the rotations at vertex $x_{n-1}$ (left) and at $y_{n-1}$ (right), respectively, are reversed.  Both embeddings are of type $c_{i+1}'$.  By Lemma \ref{lemma:c}, when the rotation at root vertex $u_n$ is reversed in either embedding, the resulting embedding is of type $a_{i}$. 


\begin{figure} [ht]  
\centering   \vskip-9pt
    \includegraphics[width=13cm]{figs-claw/c''-x,y.pdf}  \vskip-6pt
\caption{Rotation reversals at vertex $x_{n-1}$ (left) and at vertex $y_{n-1}$ (right) yield embeddings of type $c'_{i+1}$.}
\label{fig:c''-x,y}
\vskip-3pt
\end{figure}  %\vskip-12pt 
\medskip


In Figure \ref{fig:c''-z,xy} (left), the rotation at vertex $z_{n-1}$ is reversed.  The embedding is of type $c_{i+1}'$.   By Lemma \ref{lemma:c}, reversing the rotation at root vertex $u_n$ yields an embedding of type $a_{i}$.  A similar analysis applies to \hbox{Figure \ref{fig:c''-z,xy}} (right), in which the rotations at vertices $x_{n-1}$ and $y_{n-1}$ have been reversed.  Thus, the tally so far is  five embeddings of type $a_{i}$ and five of type $c_{i+1}'$.  


\begin{figure} [ht]  
\centering   \vskip-9pt
    \includegraphics[width=13cm]{figs-claw/c''-z,xy.pdf}  \vskip-6pt
\caption{Rotation reversal at vertex $z_{n-1}$ (left) yields an embedding of type $c_{i+1}'$, and reversals at vertices $x_{n-1}$ and $y_{n-1}$ (right) also yield type $c_{i+1}'$.}
\label{fig:c''-z,xy}
\vskip-3pt
\end{figure}  %\vskip-12pt 
\smallskip



In Figure \ref{fig:c''-xz,yz} (left), the rotations at vertices $x_{n-1}$ and $z_{n-1}$ are reversed.  The embedding is of type $c_{i+1}'$.  By Lemma \ref{lemma:c}, reversing the rotation at root vertex $u_n$ yields an embedding of type $a_{i}$.   When the rotations at vertices $y_{n-1}$ and $z_{n-1}$ have been reversed, as in \hbox{Figure \ref{fig:c'-xz,yz}} (right), the resulting embedding is again of type $c_{i+1}'$.  By Lemma \ref{lemma:c}, reversing the rotation at root vertex $u_n$ again yields an embedding of type $a_{i}$. 
\smallskip


\begin{figure} [ht]  
\centering   \vskip-9pt
    \includegraphics[width=13cm]{figs-claw/c''-xz,yz.pdf}  \vskip-18pt
\caption{Rotation reversals at vertices $x_{n-1}$ and $z_{n-1}$ (left) yield type $c_{i+1}'$, as do reversals at $y_{n-1}$ and $z_{n-1}$ (right).}
\label{fig:c''-xz,yz}
\vskip-3pt
\end{figure}  %\vskip-12pt 
\smallskip


\enlargethispage{12pt}

In Figure \ref{fig:c''-xyz}, the rotation at the three vertices $x_{n-1}$, $y_{n-1}$, and $z_{n-1}$ are reversed.  The embedding is of type $c_{i+1}'$.  By Lemma \ref{lemma:c}, reversing the rotation at root vertex $u_n$ now yields an embedding of type $a_{i}$.   
\smallskip

\eject

The production  
\begin{equation}
c_i'' ~\lra~ 8a_i + 8c_{i+1}'   \label{prod:c''}
\end{equation}
summarizes the results we have considered in this proposition.
\end{proof} 
\smallskip

\begin{figure} [h!t]  % fig4.20
\centering   \vskip-9pt
    \includegraphics[width=6cm]{figs-claw/c''-xyz.pdf}  \vskip-6pt
\caption{Rotation reversals at the three vertices $x_{n-1}$, $y_{n-1}$, and $z_{n-1}$ yield an embedding of type $c_{i+1}'$.}
\label{fig:c''-xyz}
\vskip-3pt
\end{figure}  %\vskip-12pt 


\begin{thm} \label{thm:claw prods}
For $n>1$, the effect on the partitioned genus distribution from the operation of attaching another claw to the iterated claw $(Y_{n-1},u_{n-1})$ corresponds to the following three productions:

\begin{alignat}{7}
\noalign{\vskip-18pt}
&a_i  \;\lra\;   &&\phantom{\;+\;} 12b_{i+1} &&\;+ 4c_{i+2}\label{prod:a*}\\
&b_i  \;\lra\;  ~~2a_i &&\;+ 12b_{i+1} &&\;+ 2c_{i+1} \label{prod:b*}\\
&c_i  \;\lra\;  8a_i && &&\;+  8c_{i+1} \label{prod:c*}
\end{alignat} 
\end{thm}

\begin{proof} \vskip-3pt
This theorem summarizes the results of Propositions \ref{prop:a}, \ref{prop:b}, \ref{prop:c'}, and \ref{prop:c''}.  Since Productions \eqref{prod:c'} and \eqref{prod:c''} have identical consequents, we can combine them into the single Production \eqref{prod:c*}. 
\end{proof}
%\smallskip


\begin{cor}   \label{cor:matmult}
$\ora{(Y_n,u_n)}^T =  M^n \ora{(Y_0,u_0)}^T$,  where
\begin{equation}  \label{matrix M2}
 M \,=\, \left[ \begin{matrix}
0 & 2 & 8 \\
12x & 12x & 0 \\
4x^2 & 2x & 8x 
\end{matrix} \right] 
\end{equation}
\end{cor}

\begin{proof} This follows from Theorem \ref{thm:claw prods}, because an increment of $r$ in the genus of an embedding surface corresponds to multiplication of a monomial by $x^r$.  
\end{proof}


Corollary \ref{cor:matmult} is equivalent to the system \eqref{rec:simult} of simultaneous recurrences and to the system \eqref{rec:GF} of generating functions.
\smallskip


\begin{example} \label{ex:values}
We now use Corollary \ref{cor:matmult} to calculate the pgd-vectors for the first four iterated claws.
\begin{align*}
\ora{(Y_1,u_1)} &\,=\, \left[ 16x,\, 24x,\, 24x^2 \right] \\
\ora{(Y_2,u_2)} &\,=\, \left[ 48x+192x^2,\, 480x^2,\, 48x^2+256x^3 \right] \\
\ora{(Y_3,u_3)} &\,=\, \left[ 1344x^2+2048x^3,\, 576x^2+8064x^3,\, 1536x^3+2816x^4 \right] \\
\ora{(Y_4,u_4)} &\,=\, \left[ 1152x^2+28416x^3+22528x^4,\, 23040x^3+121344x^4,\, \right. \\
& \hskip2in \left. 1152x^3+33792x^4+30720x^5 \right]  
\end{align*}
\noi These results agree with the results of a computer-programmed execution of the Heffter-Edmonds algorithm. 
\end{example}


We observe that the matrix $M$ corresponds to a transpose of a matrix formed from the consequents  (expressions at the heads of the arrows) of the productions in Theorem \ref{thm:claw prods}.  For such correspondence to a system of productions, we call it the \mdef{production matrix}. 




\bigskip
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{\large{Conclusions} \label{sec:conclusions}}  % sec5 

More than half of this paper is devoted to derivation of the productions.  Our list of partials at the beginning of Section \ref{sec:prod} is very much after the fact.  That is, going through the details of such derivations, during which one learns, for instance, that type $c$ needs to be split into two subtypes, is how one establishes a complete set of partials.  The number of partials is quite often ten or more.  It grows super-exponentially with the number of roots and the maximum degree \cite{Gr12}.  The size of the production matrix grows according to the number of partials.  The general method for deriving a production matrix or its equivalent is face-tracing, as exemplified here. However, once one has proved that the number of partials required is small, as for iterated claws, it may be possible to do a hand calculation of the pgd-vectors for a few small cases, and to then use them to solve equations with the production matrix entries as unknowns for the values of those entries of the matrix.  We are indebted to an anonymous referee for pointing this out.  

The data in Example \ref{ex:values} suggest some interesting additional investigation.  It is easy enough to recognize that the evenness of all the values is an immediate consequence of the fact that the mirror image of every embedding is another embedding of the same partial type in the same surface.  Many of the values are divisible by 6, which is the order of $Aut(Y_n,u_n)=\D_3$.  The relationship between the automorphism group of a graph and the partitioned genus distribution is a topic ripe for investigation.  Not even for small graphs is it well understood.  



\bigskip
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{thebibliography}{99}
	
\bibitem[Bo98]{Bo98} H.L. Bodlaender,
	Tutorial: a partial $k$-arboretum of graphs with bounded treewidth,
		\textsl{Theoretical Computer Science} \textbf{209} (1998), 1--45.

\bibitem[Ch66]{Ch66} G.J. Chaitin,
	On the length of programs for computing finite binary sequences,
	\textsl{J.\ Assoc.\ Comp.\ Mach.} \textbf{13} (1966), 547--569.  

\bibitem[FGS89]{FGS89}  M.L.~Furst, J.L.~Gross and R.~Statman,  
	Genus distribution for two classes of graphs, 
	{\sl J.~Combin.~Theory (B)} \textbf{46} (1989),  22--36.

\bibitem[Gr11a]{Gr11a} J.L. Gross, 
	Genus distribution of graph amalgamations: Self-pasting at root-vertices, 
	{\sl Australasian J. Combin.} \textbf{49} (2011), 19--38. 

\bibitem[Gr11b]{Gr11b}  J.L.~Gross, 
	Genus distributions of cubic outerplanar graphs,
  	 \textsl{J. of Graph Algorithms and Applications} \textbf{15} (2011), 295--316.
   
\bibitem[Gr12]{Gr12}  J.L. Gross, 
	Embeddings of graphs of fixed treewidth and bounded degree, 
	Abstract 1077-05-1655, \textsl{Boston Meeting of the Amer.~Math.~Soc.} (Jan.~2012). 

\bibitem[Gr13]{Gr13}  J.L.~Gross, 
	Embeddings of cubic Halin graphs: genus distributions,
	\textsl{Ars Math.~Contemporanea} \textbf{6} (2013), 37--56, online June 2012.

\bibitem[GF87]{GF87} J.L.~Gross and M.L. Furst, 
	Hierarchy for imbedding-distribution invariants of a graph,
	\textsl{J. Graph Theory} \textbf{11} (1987), 205--220.  

\bibitem[GKP10]{GKP10}  J.L. Gross, I.F. Khan, and M.I. Poshni,  
	Genus distribution of graph amalgamations: Pasting at root-vertices, 
	{\sl Ars Combin.} \textbf{94} (2010), 33-53

\bibitem[GrKo12]{GrKo12}  J.L. Gross and M. Kotrbcik,
	Genus distributions of cubic series-parallel graphs,
	draft manuscript (2012), 18pp. 

\bibitem[GMTW13a]{GMTW13a}  J.L. Gross, T. Mansour, T.W.Tucker, and D.G.L. Wang,  
	Log-concavity of combinations of sequences and applications to genus distributions,  
	manuscript (2013), 27pp.

\bibitem[GMTW13b]{GMTW13b} J.L. Gross, T. Mansour, T.W.Tucker, and D.G.L. Wang, 
	Iterated claws have real-rooted genus polynomials,  
	keynote presentation at the GEMS Conference (July, 2013), 12pp.

\bibitem[GMTW13c]{GMTW13c} J.L. Gross, T. Mansour, T.W.Tucker, and D.G.L. Wang, 
	Log-concavity of the genus polynomials of Ringel ladders,   
	manuscript (July, 2013), 17pp.

\bibitem[GRT89] {GRT89}  J.L. Gross, D.P. Robbins, and T.W. Tucker,
	Genus distributions for bouquets of circles,
	\textsl{J.\ Combin.\ Theory Ser. B} \textbf{47} (1989), 292--306.

\bibitem[GrTu87]{GrTu87} J.L. Gross and T.W. Tucker, 
	{\sl Topological Graph Theory}, Dover, 2001; (original edn. Wiley, 1987).

\bibitem[KPG10]{KPG10}  I.F. Khan, M.I. Poshni, and J.L. Gross,  
	Genus distribution of graph amalgamations at roots of higher degree,
	\textsl{Ars Math.~Contemporanea} \textbf{3} (2010), \hbox{121--138}. 

\bibitem[KPG12]{KPG12}  I.F. Khan, M.I. Poshni, and J.L. Gross, 
	Genus distribution of $P_3\Box P_n$,
	\textsl{Discrete Math.} \textbf{312} (2012), 2863--2871. 

\bibitem[Ko65]{Ko65} A.N. Kolmogorov, 
	Three approaches to the quantitative definition of information,
	\textsl{Problems Inform.\ Transmission} \textbf{1} (1965), 1--7. 

\bibitem[NSW71]{NSW71}
	E.A. Nordhaus, B.M. Stewart, and A.T. White.
	On the maximum genus of a graph, 
	\textsl{J. Combin.\ Theory Ser.\ B} \textbf{11} (1971), 258--267.
	
\bibitem[PKG10]{PKG10}  M.I. Poshni, I.F. Khan, and J.L. Gross,  
	Genus distribution of edge-amalgamations, 
	\textsl{Ars Math.\,~Contemporanea} \textbf{3} (2010), 69--86. 

\bibitem[PKG11]{PKG11}  M.I. Poshni, I.F. Khan, and J.L. Gross,  
	Genus distribution of 4-regular outerplanar graphs, 
	\textsl{Electronic J. Combin.} \textbf{18} (2011), \#P212.  

\bibitem[PKG12]{PKG12}  M.I. Poshni, I.F. Khan, and J.L. Gross,  
	Genus distribution of graphs under self-edge-amalgamations, 
	\textsl{Ars Math.\,Contemporanea} \textbf{5} (2012), 127--148. 

\bibitem[RY68]{RiYo68} G. Ringel and J.W.T. Youngs,
	Solution of the Heawood map-coloring problem,
	\textsl{Proc./ Nat. Acad./ Sci. USA} \textbf{60} (1968), 438--445.

\bibitem[Stah91]{Stah91} S. Stahl, 
	Permutation-partition pairs III: Embedding distributions of linear families of graphs, 
	\textsl{J. Combin.\ Theory Ser.\ B} \textbf{52} (1991), 191--218.

\bibitem[Stah97] {Stah97} S. Stahl, 
	On the zeros of some genus polynomials,
	\textsl{Canad. J. Math.} \textbf{49} (1997), 617--640.
	
\end{thebibliography}



\end{document}   %%















\bigskip
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{thebibliography}{99}

\bibitem[BWGT09]{BWGT09} L. W. Beineke, R. J. Wilson, J. L. Gross, and T. W. Tucker, Editors,
	\textsl{Topics in Topological Graph Theory}, Cambridge Univ.~Press, 2009.

\bibitem[Bo96]{Bo96} H. L. Bodlaender, 
	A linear-time algorithm for finding tree-decompositions of small treewidth,
	{\sl SIAM J. Comput.} \textbf{25} (1996), 1305--1317. 

\bibitem[Bo98]{Bo98} H. L. Bodlaender, 
	A partial $k$-arboretum of graphs with bounded treewidth,
	{\sl Theoretical Comp.~Sci.} \textbf{209} (1998), 1--45. 

\bibitem[FGS89]{FGS89}  M.~L.~Furst, J.~L.~Gross and R.~Statman,  
	Genus distribution for two classes of graphs, 
	{\sl J.~Combin.~Theory (B)} \textbf{46} (1989),  22--36.

\bibitem[Gr10]{Gr10} J. L. Gross, 
	Genus distribution of graphs under surgery: adding edges and splitting vertices, 
	\textsl{New York J. Math.} \textbf{16} (2010), 161--178.

\bibitem[Gr11a]{Gr11a} J. L. Gross, 
	Genus distribution of graph amalgamations: Self-pasting at root-vertices, 
	{\sl Australasian J. Combin.} \textbf{49} (2011), 19--38. 

\bibitem[Gr11b]{Gr11b}  J.~L.~Gross, 
	Genus distributions of cubic outerplanar graphs,
  	 \textsl{J. of Graph Algorithms and Applications} \textbf{15} (2011), 295--316.
   
\bibitem[Gr13]{Gr13}  J.~L.~Gross, 
	Embeddings of cubic Halin graphs: a surface-by-surface inventory,
   	Preprint, 2011, 20 pages.

\bibitem[GKP10]{GKP10}  J. L. Gross, I. F. Khan, and M. I. Poshni,  
	Genus distribution of graph amalgamations: Pasting at root-vertices, 
	{\sl Ars Combin.} \textbf{94} (2010), 33-53

\bibitem[GrTu87]{GrTu87} J. L. Gross and T. W. Tucker, 
	{\sl Topological Graph Theory}, Dover, 2001; (original edn. Wiley, 1987).

\bibitem[KMR09]{KMR08} K. Kawarabayashi, B. Mohar, and B. Reed, 
	A simpler linear time algorithm for embedding graphs into an arbitrary surface and the genus of graphs of bounded tree-width,
	\textsl{Proc.~49th Ann.~Symp. on Foundations of Computer Science (FOCS'08)} IEEE (2008), 771--780.  

\bibitem[KPG10]{KPG10}  I. F. Khan, M. I. Poshni, and J. L. Gross,  
	Genus distribution of graph amalgamations at roots of higher degree,
	\textsl{Ars Math.~Contemporanea} \textbf{3} (2010), 121--138. 

\bibitem[KPG12]{KPG12}  I. F. Khan, M. I. Poshni, and J. L. Gross,  
	Genus distribution of $P_3\times P_n$,
	\textsl{Discrete Math.}, to appear.  

\bibitem[MoTh01]{MoTh01} B. Mohar and C. Thomassen, 
	\textsl{Graphs on Surfaces}, Johns Hopkins University Press, 2001. 

\bibitem[PKG10]{PKG10}  M. I. Poshni, I. F. Khan, and J. L. Gross,  
	Genus distribution of edge-amalgamations, 
	\textsl{Ars Math.~Contemporanea} \textbf{3} (2010), 69--86. 

\bibitem[PKG11]{PKG11}  M. I. Poshni, I. F. Khan, and J. L. Gross,  
	Genus distribution of 4-regular outerplanar graphs, 
	\textsl{Electronic J. Combin.} \textbf{18} (2011) \#P212, 25pp.  

\bibitem[PKG12]{PKG12}  M. I. Poshni, I. F. Khan, and J. L. Gross,  
	Genus distribution of graphs under self-edge-amalgamations, 
	\textsl{Ars Math.~Contemporanea} \textbf{5} (2012), 127--148.  
	
\bibitem[\v{S}i\v{S}k88]{SiSk88} J. \v{S}ir\'a\v{n} and M. \v{S}koviera,
	Relative embeddings of graphs on closed surfaces,
	\textsl{Math.~Nachr.} \textbf{136} (1988), 275--284.

\bibitem[Th89]{Th89}  C. Thomassen, 
	The graph genus problem is NP-complete, 
	\textsl{J. Algorithms} \textbf{10} (1989), 568--576. 
	
\bibitem[Th97]{Th97}  C. Thomassen, 
	The genus problem for cubic graphs, 
	\textsl{J.~Combin.~Theory (B)} \textbf{69} (1997),  52--58. 
	
\bibitem[WaCo83]{WaCo83}  J. A. Wald and C. J. Colbourn, 
	Steiner trees, partial 2-trees, and minimum IFI networks,
	\textsl{Networks} \textbf{13} (1983), 159--167. 

\bibitem[Xu79]{Xu79} N.H. Xuong, 
	How to determine the maximum genus of a graph,
	\textsl{J. Combin.\ Theory Ser. B} \textbf{26} (1979), 217--225. 

\end{thebibliography}



\end{document}







\end{document}