ARS MATHEMATICA CONTEMPORANEA ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 15 (2018) 267-295 https://doi.org/10.26493/1855-3974.939.77d (Also available at http://amc-journal.eu) Calculating genus polynomials via string operations and matrices Jonathan L. Gross * Dept. of Computer Science, Columbia University, New York, NY 10027, USA Imran F. Khan PUCIT, University of the Punjab, Lahore 54000, Pakistan Toufik Mansour Department of Mathematics, University of Haifa, 3498838 Haifa, Israel Thomas W. Tuckerf Dept. of Mathematics, Colgate University, Hamilton, NY 13346, USA Received 21 September 2015, accepted 27 November 2017, published online 20 June 2018 To calculate the genus polynomials for a recursively specifiable sequence of graphs, the set of cellular imbeddings in oriented surfaces for each of the graphs is usually partitioned into imbedding-types. The effects of a recursively applied graph operation t on each imbedding-type are represented by a production matrix. When the operation t amounts to constructing the next member of the sequence by attaching a copy of a fixed graph H to the previous member, Stahl called the resulting sequence of graphs an H-linear family. We demonstrate herein how representing the imbedding types by strings and the operation t by string operations enables us to automate the calculation of the production matrices, a task requiring time proportional to the square of the number of imbedding-types. Keywords: Graph imbedding, genus polynomial, production matrix, transfer matrix method. Math. Subj. Class.: 05A15, 05A20, 05C10 * J. L. Gross is supported by Simons Foundation Grant #315001. tT. W.Tucker is supported by Simons Foundation Grant #317689. E-mail addresses: gross@cs.columbia.edu (Jonathan L. Gross), imran.farid@pucit.edu.pk (Imran F. Khan), tmansour@univ.haifa.ac.il (Toufik Mansour), ttucker@colgate.edu (Thomas W. Tucker) Abstract ©® This work is licensed under https://creativecommons.org/licenses/by/3.0/ 268 Ars Math. Contemp. 15 (2018) 441-466 1 Introduction The genus polynomial of a graph G is defined to be the generating function rG (z) = £ gi(G)zi, i> 0 where gi(G) counts the cellular imbeddings of G in the closed oriented surface Si of genus i. Following their introduction by [12] in 1987, and starting with the work of [6], the genus polynomials for a recursively constructed sequence of graphs have most frequently been calculated, as in [8, 9, 13], by partitioning the imbeddings according to the cyclic orderings of occurrences of root-vertices on the face-boundary walks (abbr. fb-walks) of the imbeddings. In this paper, we describe how to expedite such calculations. 1.1 Rotation systems All our graphs come with a labeling of the edges. All graph imbeddings in this paper are assumed to be cellular, that is, each component of the complement of the imbedded graph is homeomorphic to the interior of the unit disk. All surfaces are assumed to be closed and oriented. To describe the imbeddings of a graph G, we assign + and - orientations to the edges, including self-loops. Then any imbedding defines, for each vertex, a cyclic order of the signed edge-ends initiating at that vertex, which is called the rotation at that vertex. The rotations collectively form a rotation system (e.g., see [19]), which acts as a permutation p on the oriented edge set. If A is the involution that reverses the orientation of each edge, then the face boundary walks of the imbedding are the orbits of the permutation pA. A rotation system for a graph has also been called a "ribbon graph" or a "fat graph", especially in the context of algebraic geometry, Riemann surfaces, and the theory of dessins ([3, 20, 24]). We use the Euler polyhedral formula |V |-| E | + IF | = 2 - 27(S) to compute the genus y(S) of the imbedding surface S. Two imbeddings b1,b2: G ^ S determine the same rotation system if and only if there is a homeomorphism of the surface S taking i\(G) to 12(G) that acts as the identity isomorphism on the graph G (i.e., respects the labeling of edges). Accordingly, there is a bijection from the set of imbeddings of G to the set of rotation systems. A problem in calculating genus polynomials is that the number of possible cyclic orderings of the edge-ends incident at a d-valent vertex is (d — 1)!. Thus, the number of imbeddings of a graph G is the product n(dv — 1)!, taken over all vertices v of G, where dv is the valence of v. It is well-known [30] that the problem of calculating the minimum genus of a graph is NP-hard, even when the graph is 3-regular. It follows that calculating the genus polynomial is at least that hard. For example, the number of rotation systems for the complete graph K7 is (5!)7 « 3.6 x 1014, and the genus polynomial for K7 has only recently been computed [2]. Table 1 gives the list of coefficients. J. L. Gross et al.: Calculating genus polynomials via string operations and matrices 269 Table 1: Genus distribution of the complete graph K7. 1 9i 0 0 1 240 2 3,396,960 3 3,746,107,320 4 594,836,922,960 5 20,761,712,301,960 6 158,500,382,165,280 7 178,457,399,105,280 1.2 Context Genus polynomials for recursively specified families of graphs have been computed mostly within a general paradigm in which the recursive operation occurs in the vicinity on a small number of vertices or edges designated as roots. The set of all imbeddings of each graph in the family is partitioned into what we now call imbedding-types, according to incidence of the fb-walks on the roots, a technique for calculating genus polynomials that was introduced by [6]. This basic paradigm is exemplified by [8, 13] for root-vertices, and by [25, 26] for root-edges. This paper integrates several embellishments of the basic paradigm: • The genus polynomial for a graph is partitioned into a pgd-vector, with one coordinate for each imbedding type, such that each coordinate is a polynomial that gives the number of oriented imbeddings of that imbedding type in every orientable surface. • The recursively applied topological operation is represented by a production system, as developed by Gross, Khan, and Poshni, in a series of papers [8, 13, 25, 26], that transforms the pgd-vector for a given graph into the pgd-vector for the graph resulting from an application of the recursive operation used to specify the graph family. In those papers, the productions were calculated with the aid of a multiplicity of drawings of rotation projections. • The representation of production systems by matrices was introduced by Stahl [27], for application to pgd-vectors of some graphs in what he called H-linear families. Such matrices are now called production matrices, and the graph sequences are now called H-linear sequences, or simply linear sequences. Stahl used what he called permutation-partition pairs to derive production matrices. • The representation of imbedding-types by strings of root-vertices, as developed by Gross [11]. • Using string operations directly to calculate the production matrices, as suggested subsequently by Mohar [23]. The general idea of a linear sequence is that a copy of a graph H is attached to each graph in the sequence to form the next graph in the sequence. It is necessary to attach each copy of H in the same way, as described precisely by [4]. 270 Ars Math. Contemp. 15 (2018) 441-466 1.3 Outline of this paper Our main focus in this paper is the calculation of production matrices. Since the size of the matrix increases with the number of imbedding types, and since the number of imbedding-types grows exponentially with the number of roots and with the valences of the roots, most of the calculations of genus polynomials have been for sequences of graphs with at most two roots and valences no larger than 4. The string notation by which we concisely represent imbedding types allows us to automate the bookkeeping used in tracking the way imbedding types are changed by the addition of paths between root vertices. The advantages of this system are many. It allows us to derive in a few lines (see Subsection 4.3) the computation of production matrices that formerly involved many figures [10] or detailed paper-and-pencil applications of what Stahl [28] called the "Walkup reduction" for permutation-partition pairs. String notation facilitates the computer calculation of production matrices whose derivation would be un-feasibly tedious by hand (see the 12 x 12 matrix in Section 5). Finally, it reveals ways of combining different imbedding types to get smaller matrices (see Subsection 5.1). Following a review in Section 2 of the representation of imbedding-types by strings, Section 3 introduces the representation of topological and vertex-labeling operations on imbeddings by string operations. Section 3 also introduces the concept of grouping two or more i-types into a "super-type". As an illustration of how the string operations are used in calculations of genus distributions, Section 4 applies these representations to two previously published examples, one of which (the iterated claw) we have adapted here to give a detailed example of grouping. Also, we explain in Section 4 how our use of productions to calculate pgd-vectors is interpretable as an embellishment of the transfer matrix method, along the lines described by [29]. Section 5 explores issues related to computation. It uses the theory developed in the previous sections to calculate genus polynomials for a vertex-amalgamation path of copies of K4 and for an edge-amalgamated path of copies of K4. Without string operations, both derivations would be long and tedious. We used two computational aids while preparing this paper. • The computational system Maple®. • A computer program, based on string operations, that calculates production matrices. Such kinds of aids are what we have in mind in various comments here, rather than a state-of-the-art computer. Section 5 includes an additional example of the grouping of i-types into a super-type. In Section 6, we use Burnside's Lemma to derive a formula for the maximum number of imbedding types for a graph with two roots of any possible combination of valences. We generalize the formula to more that two roots. From the rapid growth rate of the number of imbedding-types, as valences and the number of roots of the graphs at issue increases, it becomes clear that programmable computation tools are a virtual necessity when seeking to calculate genus polynomials. 2 Representing imbedding-types by strings In this section, we develop a system of notation that uses strings of root-labels, so that representing the addition of an edge to a graph becomes a simple matter of applying a few string-processing rules. J. L. Gross et al.: Calculating genus polynomials via string operations and matrices 271 2.1 Face-boundary-walks We assign labels 0,1,2,... to the roots of a graph G. Given an imbedding of G, we represent a face as a string of roots, in the order they are encountered in a traversal of its fb-walk following the orientation of the surface. If an fb-walk does not contain any roots, we call its string empty. Two strings are equivalent representations of an fb-walk if one is a cyclic shift of the other. We denote an entire equivalence class of strings by putting a representative string of labels inside parentheses. The canonical representative for the equivalence class of fb-walks is the one with minimum lexicographic order with respect to the labels 0,1,... . Remark 2.1. Vertices that are not roots do not appear in the string representing a face. Accordingly, the appearance of consecutive labels... 12 ... within a string would not imply that there is an edge between vertices 1 and 2. Also, since any labeled vertex may appear more than once around an fb-walk, the corresponding cyclic list of root-labels is not a permutation. 2.2 Imbedding types The collection of non-empty strings for all the fb-walks of an oriented imbedding of a rooted graph G is called an imbedding-type of G (abbr. i-type). The collection of all imbedding types over all imbeddings of G is called the full collection of imbedding types for G. In order to compare imbedding types for the same rooted graph, we usually use the shortlex order [31] on canonical representatives to make a list of fb-walks (rather than a set): shorter faces are listed before longer ones, and if two faces have the same length, the one with shortlexically least canonical representative is listed first. We call such a list the canonical form for the i-type. Example 2.1. Figure 1 shows an imbedding of K4 in the sphere with roots 0,1,2, and 3. If the "interior" fb-walks are oriented counterclockwise (which forces the "exterior" fb-walk to appear as clockwise, from the perspective of vertex 0), then the i-type (in canonical form) is Notice that each face is represented by its canonical form (cyclic shift with least lexicographic order) and that the faces are listed in shortlex order. Since for this example every vertex is a root, it follows that two consecutive vertices (with respect to cyclic order) in the (012)(023)(031)(132). Figure 1: An imbedding of K4 in S0. 272 Ars Math. Contemp. 15 (2018) 441-466 representation of a face actually does represent a directed edge. For any two roots i and j, the directed edge ij appears exactly once. If i = 0 and j = 1, we could suppress the labels 2,3 to obtain the i-type (01)(0)(01)(1) = (0)(1)(01)(01) for the imbedding of Figure 1. If the only root is 0, then the imbedding type would be (0)(0)(0). Notice in the last imbedding type, the number of strings is less than the number of faces, because the fb-walk (132) contains no instances of vertex 0, and we do not list empty faces. If we reverse the orientation of the sphere and have all four vertices 0,1,2,3 as roots, then the i-type in canonical form would be (021)(032)(013)(123) = (013)(021)(032)(123). Observe that the shortlex order for the faces differs from the previous orientation. However, the i-type for roots 0, 1 is the same as before, as is the i-type for root 0, when labels 1, 2, and 3 are suppressed. Example 2.2. Considering all 24 rotation systems for K4, we get the following census of i-types for roots 0,1, given in shortlex order: • 2 of i-type (0)(1)(01)(01) • 2 of i-type (0)(01011) • 2 of i-type (1)(00101) • 2 of i-type (01)(0011) • 8 of i-type (01)(0101) Notice that since there is only one edge 01, only one of the substrings 01 in an i-type, for example (01)(0101), comes from an edge. The other juxtapositions of 0 and 1 come from suppressing incidences of the roots 2 and 3. We conclude that {(0)(1)(01)(01), (0)(01011), (1)(00101), (01)(0011), (01)(0101)} is a full set of i-types for K4 with roots 0 and 1. In Section 6 of this paper, we shall see that the maximum number of i-types for a pair of 3-valent roots is 38. Remark 2.2. We observe that within the string representation of any i-type, each root-vertex appears as many times as its valence. If there is an edge between roots i and j , then both ij and ji must appear at least once in every i-type. On the other hand, as we have noted, the appearance of ij in a string does not imply that there is an edge between i and j. Remark 2.3. Suppose that G has no multi-edges or self-loops, and suppose that every vertex is a root. Then each rotation system for the graph G determines a unique i-type, since each i-type determines a rotation system for the dual graph. In this circumstance, the number of i-types would be the same as the number of rotation systems. At the opposite extreme, the set of imbeddings for a tree with one root-vertex has only one i-type. Remark 2.4. When there are multi-edges or loops and every vertex is a root, it happens that different rotation systems can determine the same i-type. For example, the bouquet Bn has only one vertex 0 and has n loops at that vertex. Then an i-type is simply a partition of 2n into k parts, where k is the opposite parity of n (k is the number of faces, so the Euler characteristic 1 - n + k must be even). Thus, the number of i-types for imbeddings of Bn with k faces is at most the Stirling subset number {2" } (i.e., the Stirling number of the second kind), where k and n have opposite parities. J. L. Gross et al.: Calculating genus polynomials via string operations and matrices 273 2.3 String notational conventions We adopt two notational conventions for strings: • The concatenation of a string S with a string T is denoted by ST. • The reverse string for a string S is denoted by S-1. We emphasize that SS-1 is not the empty string, but rather the concatenation of S with its reverse (which forms a palindrome). This notation does satisfy the relations (ST)-1 = T-1S-1 and (S-1)-1 = S as if in a group, even though our strings are not permutations (since roots can repeat), and even though they do not form a group. 2.4 Pgd-vectors Given an i-type t, we write its partial genus polynomial in the form J2aizi where ai is the number of type-t imbeddings of G of genus i. If the i-types are listed in shortlex order, then we can associate the set of partitioned genus polynomials for G with a column vector whose rth coordinate is the partial genus polynomial for the rth i-type. This is called apgd-vector for the graph G. For instance, the partitioned genus distribution for the complete graph K4 given by Example 2.2 corresponds to the vector [2 2z 2z 2z 8z]T where the superscript T denotes the transpose. 3 Operations on imbedding-types In this section, we describe how a path-adding operation affects the i-types. We also describe the relabeling of root-vertices, and the suppression of some root-labels, which are used, for instance, when there are no more paths to be added at a root-vertex. 3.1 Adding a path within a face and between faces Let G be a rooted graph and let iUj be a path whose endpoints i,j are roots of G but all other vertices of U are not in G. If U is empty, we have simply the edge ij. The effect of adding iUj into a face with fb-walk (iSjT) is given by the following operation: (iSjT) + iUj ^ (iSjU-1)(iUjT). (3.1) In calculations, we may denote the right-hand side by AddiUj [iSjT]. If the i-type in which the fb-walk (iSjT) occurs is of the form (iSjT)W1W2 ...Wk, 274 Ars Math. Contemp. 15 (2018) 441-466 which includes other fb-walks, then applying Operation (3.1) to that i-type yields the i-type (iSjU-1)(iUjT )WiW2 ...Wk. That is, the other fb-walks of the i-type are simply recopied. The effect of adding the path iUj between two faces (iS) and (jT) is given by this operation: [(iS), (jT)] + iUj ^ z(iSiUjTjU-1). (3.2) The right-hand side may be expressed as Add^ [(iS), (jT)]. When applying Operation (3.2) to an i-type with fb-walks (iS) and (jT), any other fb-walks of the i-type are simply recopied, the same as for Operation (3.1). The multiplier z indicates that the genus of the imbedding rises by 1 when a handle is added to the surface. For the circumstance in which the faces (iS) and (jT) lie within (disjoint) imbeddings i and i' of separate graphs G and G', the effect of joining the imbeddings by adding the path iUj between the two faces (iS) and (jT) is given by this operation: [(iS), (jT)] + iUj ^ (iSiUjTjU-1). (3.3) The non-presence of the multiplier z signifies the fact that the genus of the surface in which the resulting graph is imbedded is simply the sum of the genera of the imbeddings i and i'. Example 3.1. Consider an imbedding of the 4-cycle 0213 in the sphere. There are two faces, one with fb-walk (0213) and the other with fb-walk (0312). Thus, the initial i-type is (0213)(0312). There are four ways to add a path 0451 to such an imbedding, one within the face (0213), one within the face (0312) and two between the faces (0213) and (0312). Figure 2 shows the four possible ways to add the path 0U1 and the resulting i-type for each. (0213)(0312) 2 -, 0 1 (02154)(04513)(0312) 2 -, 0 1 (i) (0213)(03154)(04512) z(02130451203154) z(03120451302154) 2 2 4 (ii) 0 2 0 3 (iv) Figure 2: Adding the path 0451 to an imbedding of a 4-cycle in the sphere. 1 1 1 J. L. Gross et al.: Calculating genus polynomials via string operations and matrices 275 (i) Inserting path 0451 into the face (0213) yields the imbedding type (02154)(04513)(0312), as per Operation (3.1). We now have three faces. Root-vertices 0 and 1 now have valence 3, so they now appear three times in this representation of the i-type. (ii) Inserting the path 0451 instead into the face (0312) yields i-type (0213)(03154)(04512). (iii) If we join the two faces, from endpoint 0 inside the face (0213), to endpoint 2 inside the face (0312), then the resulting string expression is z(02130451203154). (iv) If we add the path 0451 with edge-end 0 now inside the face (0312) and edge-end 1 inside the face (0213), we get the string expression z(02154031204513). It follows that the net result of adding the path 0451 to the i-type (0213)(0312) is the following linear combination of i-types taken over the ring Z[z] of polynomials with integer coefficients: (02154)(04513)(0312) + (0213)(03154)(04512) + z(0213045120354) + z(03120451302154). Remark 3.1. The path ii for adding a self-loop is simply a special case. As a variation on Operation (3.1), we have (iS) + ii ^ (i)(iSi) As a variation on Operation (3.2), we have [(iS), (iT)] ^ z(iSiiTi) Remark 3.2. If a graph already has an edge ij, then adding the path P = ij creates a multiple adjacency. 3.2 Suppressing roots and relabeling roots Given a subset of roots {i, j,... }, the root-suppression operator Supi j acts to suppress every occurrence of the root-labels i, j,... within an i-type t. For example, SuPi,2 [(1)(12)(0212)(0231303)] = (0)(03303). Observe that we delete empty pairs of parentheses as a final step in suppressing roots. 276 Ars Math. Contemp. 15 (2018) 441-466 Example 3.1, continued. Suppressing roots 2 and 3 as well as any roots along U transforms the i-type (021U-1)(0U 13)(0312) into the i-type (01)(01)(01). Similarly, Sup12U [z(021U-1 )(0U 13)(0312)] = z(010101). Moreover, when root-suppression is applied to a linear combination of i-types, it can reduce the number of terms. For instance, Sup2,3U [(021U-1)(0U 13)(0312) + (0213)(031U-1)(0U 12) + z(02130U 1203U-1) + z(03120U 13021U-1)] = 2(01)(01)(01) + 2z(010101). We can also relabel roots, by using the root-relabeling operator. Suppose that the label i appears in i-type t and label j does not. Then Labj [t] is the i-type obtained by replacing in t all occurrences of i by j. Thus, Lab24[(1)(2)(22)(1323)] = (1)(4)(44)(1343). We denote by Lab^y,... [t] the result of relabeling i by i', j by j' etc. 3.3 Reversing orientation If the orientation of a graph imbedding is reversed, the effect on i-types is as follows: • the cyclic order of each fb-walk is reversed; • the genus of the imbedding stays the same. We call this the i-type reversal operator. Given an i-type t, we denote by t-1 the i-type in which each fb-walk string is reversed. Note that if (ST) is an fb-walk within i-type t, then the corresponding fb-walk in t-1 is (T-1S-1), for which a cyclic shift gives (S-1T-1). On the other hand, the i-type (R-1S-1T-1) is not a cyclic shift of the i-type (RST)-1 = (T-1S-1R-1). Proposition 3.3. The i-type reversal operator commutes with the operators Add, Sup, and Lab. Proof. Clearly, we can reverse lists either before of after suppressing or relabeling vertices, and the result is the same. Using Rule (3.1) for adding a path within a face, we have Addp [(iSjT )]-1 = [(SP-1)(PT)] = (T-1P-1)(S-1P) and (3.4) AddP [(iSjT )-1] = AddP [iT-1jS-1] = (T-1P-1)(S-1P) (3.5) Using Rule (3.2) for adding an edge between two faces, we have Addp[(iS), (jT)]-1 = z(PTP-1S)-1 = z(S-1PT-1P-1) and (3.6) Addp[(iS)-1, (jT)-1] = Addp[(iS-1), (jT-1)] = z(PT-1P-1S-1) (3.7) □ J. L. Gross et al.: Calculating genus polynomials via string operations and matrices 277 3.4 Combining i-types into super-types As we have observed, the number of i-types grows exponentially with the valence and the number of roots, so any way of reducing the number of i-types is welcome. For example, in building a graph by path-addition, we can always group an i-type with its reverse, since i-type reversal commutes with edge path-adding. Indeed, root-suppression is also a way of grouping many i-types together. Suppose that the rooted graph H is obtained from the rooted graph G by a sequence Op of the following kinds of operations: path-additions, root-suppression, and root-relabeling. Let T be the full collection of i-types for G, and let S be the full collection of i-types for H, both in shortlex order. Then for any i-type t G T, we see that The expression Op (t) is a linear combination of elements of S, with coefficients taken from the ring Z[z] of polynomials in z. We represent Op, therefore, as a matrix M whose columns are labeled by i-types in S, and whose rows are labeled by i-types in T, where Ms,t is the coefficient of i-type s in the expression Op(t). Let P and Q be partitions of S and T, respectively. Suppose that we order the i-types within S and the i-types within T so that the i-types within each cell of P and within each cell of Q are contiguous in the respective orderings, inducing a partitioning of the production matrix M into blocks that satisfy this criterion: Within each block, the column sums are the same. (This requirement applies also to the blocks that span only a single row of the matrix M, which implies that the entries in such a row are identical.) Then we call the partitions P and Q compatible with M. Moreover, we call each part of P and Q a super-type for the operation Op. We can then condense the matrix M to a smaller one whose columns are indexed by P and rows by Q, and whose entries are the constant column sum of the block of M determined by the respective parts. We have already encountered super-types in two contexts: type-reversal and root-suppression. For type-reversal, we partition a full collection of i-types into parts by grouping together an i-type and its reverse. Since type-reversal commutes with path-adding, root-suppression, and root-relabeling, it is compatible with any sequence of those operations. We can also view root-suppression Supi j itself as creating super-types. In this case, we have S = T. The parts of P are just singletons; i-types s, t are in the same part of Q if and only if Supi j ... (s) = Supi j ... (t). Notice in this case, the matrix M is just the identity matrix and each block is a part of a single column of M. The condensed matrix has a single 1 in each column. Another way to create super-types is to exploit any symmetry between roots. With H, G, S, T as before, suppose there is a graph automorphism f of H that permutes the roots of H and G. Then f also induces a permutation of the S and T. We can then use orbits of that permutation as super-types. Grouping types into super-types by graph automorphisms and reversal is illustrated particularly well in the family of iterated claws in Subsection 4.3, where 12 i-types are reduced to three super-types. For now we consider an example that provides a clear illustration of the theory underlying the reduction. 278 Ars Math. Contemp. 15 (2018) 441-466 Example 3.2. Suppose that G = K4, as in Example 2.2, with roots 0 and 1, and that the graph H is obtained from G by the operation of adding a second edge between 0 and 1. Since there is an automorphism of the graph G interchanging 0 and 1, we have the partition given in Table 2 for the full set T of i-types of the graph G, under the partition Q (induced by this automorphism), with the parts of Q indicated by square brackets. Table 2: Partitioning the i-types for (K4, {0,1}). T _T /Q (0)(1)(01)(01) (0)(1)(01)(01) (0)(01011) [(0)(01011), (1)(00101)] (1)(00101) (01)(0011) (01)(0011) (01)(0101) (01)(0101) We can construct the full set S of 13 i-types for the graph H, by adding the path 01 to the i-types in T for the graph G. In Table 3, we again use square brackets to enclose the parts of the partition P. Table 3: Partitioning the i-types for (K4 +01, {0,1}). Vh(z) Figure 5: Functor from the category of graphs and string operations to the category of ring modules and matrices with integer polynomial coefficients. T 4.4 Polynomial matrix and transfer matrix methods There are models in the physical sciences where the computational process uses polynomial matrix entries, like our production matrices. Some such models in chemistry were explored in [21, 22], which uses the terminology polynomial matrix method. This method was adapted by [1] for application to matching polynomials of polygraphs. As described by [7], the transfer matrix method for various mathematical contexts concerns the transformation of a given problem into a matter of counting walks in a digraph. We observe that if A is the adjacency matrix of a digraph, then the ij entry of the matrix Ak counts the numbers of paths from vertex v to vertex vj. A generalization of this problem (see [29]) is concerned with a digraph in which the arc from vertex i to vertex j, for all i and j, is labeled with the element m^j of a commutative J. L. Gross et al.: Calculating genus polynomials via string operations and matrices 285 ring, with M = (m^ ). Instead of counting the paths of length k, we are calculating the sum of the products of all length-k paths from v to vj. Of course, the ij entry of the matrix Mk gives this sum for vj and Vj. In [5] and [23], the matrix M is called a "transfer matrix". When calculating pgd-vectors for a graph sequence {Gn : n = 0,1,...} that is specified by recursive application of a topological operation t, we take the imbedding types as vertices of the digraph. We label the arc from type-i to type-j by the coefficient of type-j in the production for type-i. 5 Machine computation of production matrices In this section, we give two examples of linear sequences whose production matrices have been calculated with the aid of a computer program. It should be clear that calculating these production matrices by hand would be daunting. Heretofore, such calculations have been done mostly by hand, which has limited us to calculating the genus polynomials only for relatively few graph families. As a consequence, we have very little data to study deep issues, such as the log-concavity conjecture, that the genus distribution of every graph is a log-concave polynomial (see [18, 16]). 5.1 Vertex-amalgamation path of copies of K4 We define the graph Ti to be the complete graph on four vertices, with a single root, labeled 0. The graph Tn is obtained from Tn-1 by vertex-amalgamating a new copy of K4 to Tn-1. The graphs T2 and T3 are illustrated in Figure 6. Figure 6: The graphs T2 and T3. Following the paradigm of [13], we could obtain Tn from Tn-1 by vertex-amalgamating a doubly rooted copy of K4 to a singly rooted copy of Tn-1. However, whereas a pair of 2-valent root-vertices involves at most 10 i-types, it can be seen in Table 5 that for two 3-valent root-vertices, the number of i-types could be as large as 38. Moreover, the potential number of productions for amalgamating two graphs with 38 i-types could be as large as 382 = 1444. In what follows, we see that using the string-operation paradigm enables us to reduce the number of i-types from 38 to 3. The topological operation of vertex-amalgamating an additional copy of K4 to the rooted graph (Tn-1,0) can be represented by the following sequence of string operations. Procedure 5.1. Add the next copy of K4 by vertex-amalgamation. Add0i230 Addo2 Add 13 SuPo,1,3 Lab2o (5.1) (5.2) (5.3) (5.4) (5.5) 286 Ars Math. Contemp. 15 (2018) 441-466 We see that the i-types for a graph with a single 3-valent root-vertex named 0 are (0)(0)(0) (0)(00) (000) More generally, the number of i-types for a graph with a single k-valent root-vertex equals at most the number of partitions of the integer k. Nonetheless, even though only three productions would be needed, deriving them with pencil-and-paper calculations would be tedious work. Just for a start, there are 12 ways to insert the path 01230 into an imbedding of Tn-1, two ways between each of the three pairs of distinct corners at root-vertex 0 and two ways at each corner. The total number of imbeddings of Tn that are consistent with each imbedding of Tn-1 is 480. Theorem 5.1. The pdg-vector of the graph Tn is Mn V1 is [2 12z 2z] and the production matrix is -i V1; where the initial pgd-vector Mt (z) = 96z + 18 80 z + 30 60 " 48z2 + 156z 220z 360z 144z2 + 18z 120z2+ 30z 60z (5.6) Proof. The initial pgd-vector V1 for (K4,0) and the production matrix are best calculated by a computer program. □ 5.2 Edge-amalgamation path of copies of K4 Here we define T1 to be the complete graph K4 with a single root-edge 01. The graph Tn is obtained from Tn by edge-amalgamating a copy of K4. The new root-edge is the edge in the new copy that is independent of the edge amalgamated to the previous root-edge. The graphs T2 and T3 are illustrated in Figure 7. 'V v 0 0 Figure 7: The graphs T2 and T3. The topological operation of extending the graph Tn-1 by edge-amalgamating an additional copy of K4 can be represented by the following sequence of string operations. Procedure 5.2. Add the next copy of K4 by edge-amalgamation. Addo23i Addos Add i2 Supo,i Lab 20,31 (5.7) (5.8) (5.9) (5.10) (5.11) 1 1 J. L. Gross et al.: Calculating genus polynomials via string operations and matrices 287 We determine that the i-types for the graphs Tn are as follows, grouped by classes under the automorphism interchanging 0 and 1 and listed in shortlex order: 1. (0)(1)(01)(01) 7. (01)(0011) 2. (0)(1)(0011) 8. (01)(0101) 3. (0)(01)(011), (1)(01)(001) 9. (001)(011) 4. (0)(00111), (1)(00011) 10. (000111) 5. (0)(01011), (1)(00101) 11. (001011), (001101) 6. (01)(01)(01) 12. (010101) Each imbedding of Tn-i in each of these 12 super-types has 576 possible extensions to an imbedding of Tn. Theorem 5.2. The pdg-vector of the graph Tn is M matrix is i-i (z)V(z), where the production 4 18 8 36 40 6 20 22 12 72 80 84 8z 0 16z 0 0 24z 32z 32z 32z 0 0 0 64z 96z 96z 96z 96z 96z 128z 128z 128z 0 0 0 48z2 32z2 32z2 0 0 48z2 0 0 0 0 0 0 8z 36z 16z 72z 80z 12z 40z 44z 24z 144z 160z 168z 60z 56z 72z 48z 48z 60z 64z 64z 96z 0 0 0 4z2 + 4z 48z2 + 18z 64z2 + 8z 36z 40z 72z2 + 6z 20z 22z 12z 72z 80z 84z 16z 72z 32z 144z 128z 24z 80z 72z 48z 288z 256z 240z 104z2 48z2 64z2 0 0 72z2 0 0 0 0 0 0 32z3 0 0 0 0 0 0 0 0 0 0 0 64z2 96z2 96z2 96z2 96z2 96z2 128z2 128z2 128z2 0 0 0 60z2 56z2 72z2 48z2 48z2 60z2 64z2 64z2 96z2 0 0 0 The initial graph (Ti; 0) has the pgd-vector V(z) = [2 0 0 0 4z 0 2z 8z 0 0 0 0]T. Proof. The initial pgd-vector and the production matrix were calculated by our computer program. □ If follows that T2 8 + 376z 16z + 320z2 128z+ 1664z2 96z2 16z + 752z2 120 z + 832z2 584z2 + 8z 32z + 1248z2 208z2 64z3 128z2 + 1664z3 120z2 + 832z3 and Ta 32 + 5040z + 119552z2 + 207616z3 64z + 9216z2 + 111872z3 512z + 56064z2 + 612864z3 384z2 + 28416z3 + 103424z4 64z + 10080z2 + 239104z3 + 415232z4 480z + 43200z2 + 365568z3 5872z2 + 32z + 176256z3 + 389376z4 128z + 19136z2 + 414464z3 + 644096z4 832z2 + 56704z3 + 181760z4 256z3 + 12032z4 512z2 + 56064z3 + 612864z4 480z2 + 43200z3 + 365568z4 288 Ars Math. Contemp. 15 (2018) 441-466 6 Enumerating possible imbedding types Various previously published genus polynomial calculations have involved recursive constructions of families of graphs with two 2-valent root-vertices, for which ten i-types are sufficient. As we progress toward more general results, most especially in regard to the LCGD conjecture, we are encountering recursive graph constructions for which we use arbitrarily many vertex roots, of arbitrary degrees. In this section, we first use Burnside's Lemma to calculate the number of i-types that can occur for two 2-valent roots. Then we generalize to obtain lower and upper bounds on the number of i-types for arbitrarily many root-vertices or arbitrary valences. Interestingly, our method provides a formula for calculating the number of possible cyclic partitions of a multi-set. Thus, it is a generalization of Stirling numbers of the first kind. 6.1 Two 2-valent roots Early papers on genus polynomial calculations via pgd-vectors used ten mnemonics for the i-types for graphs with two 2-valent roots. The following table lists the ten mnemonics and their corresponding type-names: dd0 dd' dd" ds0 ds' (0)(0)(1)(1) (0)(01)(1) (01)(01) (0)(0)(11) (0)(011) sd0 sd' ss0 ss1 ss2 (00)(1)(1) (001)(1) (00)(11) (0101) (0011) An ad hoc examination confirms that the ten type-names contain all the possible partitions of the multi-set {0,0,1,1} into cyclic cells. We now undertake a reconfirmation of this calculation of ten possible i-types, using Burnside's Lemma. Our set of objects is the set of disjoint cycle decompositions of the 24 permutations in the symmetric group S4, with domain {0,1,2, 3}. Our permutation group on them has the permutations e (identity) (0 2) (1 3) (0 2)(1 3) (6.1) where we regard the numbers 2 and 3 as second copies of the numbers 0 and 1, respectively. Under the action of this permutation group, the orbit of the permutation (0 1)(2)(3) is (0)(1)(2 3) (0)(3)(1 2) (1)(2)(0 3) (2)(3)(0 1) This orbit corresponds to the imbedding-type (0)(1)(01). The identity permutation e fixes all 24 disjoint cycle representations of S4. The permutation (0 2) fixes the subgroup of disjoint cycle representations in which both 0 and 2 are fixed or transposed, whose cardinality is 4. The permutation (1 3) fixes the same subgroup of cardinality 4. The permutation (0 2)(1 3) fixes that same subgroup, plus the set (0 1)(2 3) (0 3)(1 2) (0 1 2 3) (0 3 2 1) for a total of 8 fixed points. Applying Burnside's Lemma, we divide the sum of the sizes of the fixed-point sets by the cardinality of the permutation group (6.1) to obtain 24 + 4 + 4 + 8 = 40 = 4 = 4 = as the maximum number of i-types for two 2-valent roots. J. L. Gross et al.: Calculating genus polynomials via string operations and matrices 289 6.2 Two roots, 2-valent and 3-valent Suppose that root 0 is 2-valent and root 1 is 3-valent. Then there are 18 imbedding-types, as in Table 4. Table 4: Table of the i-types for two roots, one 2-valent and one 3-valent. structure imbedding types 1i (0)(0)(1)(1)(1) 13 2 (0)(0)(1)(11) (0)(1)(1)(01) (1)(1)(1)(00) 1 22 (0)(01)(11) (1)(00)(11) (1)(01)(01) 12 3 (0)(0)(111) (0)(1)(011) (1)(1)(001) 23 (00)(111) (01)(011) (11)(001) 14 (0)(0111) (1)(0011) (1)(0101) 5 (00111) (01011) The action of the permutation group £{0,2} x £{1,3,4} on the elements of £{0,1,2,3,4} has the cycle index -2 [ii + 4t3t2 + 3tit2 + 2Î2Î3]. We now consider the number of fixed points for each of the four permutation types. Type t\. The identity permutation fixes all 120 elements of £{0,1,2,3,4}. Type t\t2. Each permutation of structure tft2 fixes 12 elements of £{0,1,2,3,4}. For instance, (0 2) fixes each of the six elements with the 1-cycles (0) and (2) and each of the six with the 2-cycle (02), for a total of 12. The sum of the sized of the fixed-point sets of the four permutations of structure tft2 is 48. Type t\t2,. Each permutation of structure t1t2 fixes 8 elements of £{0,1,2,3,4}. For instance, (0 2)(1 3) fixes both of the elements with the 1-cycles (0), (2), and (4), both with the 2-cycle (02) and the 1-cycle (4), and also the four elements (0 1)(2 3), (0 3)(1 2), (0 1 2 3), and (0 3 2 1) for a total of 8. The sum of the sized of the fixed-point sets of the four permutations of structure t1t2 is 24. Type t]t3. Each permutation of structure t2t3 fixes 6 elements of £{0,1,2,3,4}. In particular, (0 )(2)(134) fixes Z{0,2} x Z{1,3,4}, as does (0)(2)(1 4 3). Together, they make a contribution of 12 to the sum of the sizes of the fixed point sets. Type t2t3. These two permutations each fix the same 6 elements of £{0,1,2,3,4} as in the preceding case, for a net contribution of 12. Applying Burnside's Lemma, we infer that the number of orbits is 120 + 48 + 24+ 12+ 12 216 12 12 = 18. 290 Ars Math. Contemp. 15 (2018) 441-466 6.3 Several roots of arbitrary degrees We now calculate lower and upper bounds on the number of i-types. Theorem 6.1. For a class of graphs with roots 0,1,..., k — 1 of respective degrees do, di,..., dk-i, the number of i-types is at least (dp + dj +-----+ dfc_i)i do!di! • • • dfc_i! (6.2) Proof. In addition to their respective primary names 0,1,..., k — 1, each root j has dj — 1 aliases chosen from among the numbers k, k +1, .. ., do + di +----+dfc_i with no two different primary names having any aliases in common. Accordingly, our set of objects is the set of disjoint cycle representations of the symmetric group , where K = d0 + di + • • • + dk-i. The permutation group that acts on them is isomorphic to X ^di X • • • X Sdfc-1 Since the identity permutation fixes all the cycle forms of , the sum of the sizes of the sets of fixed points is at least K!. The cardinality of the permutation group is di!d2! • • • dk!. Thus, by Burnside's Lemma, a lower bound on the number of i-types is given by (6.2). □ Theorem 6.2. For a class of graphs with roots 0 and 1, of respective degrees a and b, the number ofi-types is at most EnkckCk! E E E 1 c k=i yi,Pi + qi = Oi (iPi 2P2 -aPa )ePa (i9i 292 ---bib )ePb n j=i iP%Pi^Y\j = i jqj qj ! where the sumYl,c is over all partitions 1ci 2C2 • • • nCn G Pn and Pn is the set of all partitions of the number n. Proof. The action of the permutation group ^{i,3,4,...,a+i} X ^{2,a+2,a+3,...,a+b} on the elements of S{i 2,...,n}, where n = a + b, has the cycle index Ca,b = E E na=i if nb=i j (iPi 2P2 '"fflPa )£Pa (ill 292 ••• b9b )£Pb n®=i iPipi ! j jqj qj ! where Pm is the set of all partitions of m. The number of fixed points for a permutation of cycle type 1ci 2C2 • • • nCn is given by i!b!Ca,b(1Ci2c2 ••• ncn) n kckcfc!, k=i J. L. Gross et al.: Calculating genus polynomials via string operations and matrices 291 where Ca,b(1ci 2C2 • • • nCn ) is the coefficient of if t22 • • • tn in the polynomial Ca,b. Thus, each permutation of structure if t22 • • • tn fixes n kck ck ! y y y -^-. 11 k ^ ^ ^ na iPi v !fib i j a ! Vi,pi+gi=ci (ipi 2P2...apa )ePa (i«i 292 ...bib)efb i li=i i Vi! 1 ij=ij qJ ! k=i elements of £{1j2i...jn}. Applying Burnside's Lemma, we conclude that the number of orbits is given by 1 ^a^nk Ck ! E E E na iPi ^b iqj ! k = 1 Vi,pi+qi=ci (iP1 2P2 ...aPa )ePa (191 292 ...b9b 14=1' yj- i!6! which equals 1 IT k Ck' ^ ' ^ ' no I pr b -q. | ' c fc=1 Vi,pi + qi = ci (1P1 2P2 ...apa )ePa (1*1 2*2 b !j=1 % %Pi'l i j = 1 j ° Qj ' where the sum J2c is over all partitions 1C12C2 • • • nCn e Pn. Applying our formula for a,b < 10, we obtain Table 5. Table 5: The maximum number of i-types for two root-vertices, of valences a and b. □ a\b 1 2 3 4 5 6 7 8 9 10 1 2 4 7 12 19 30 45 67 97 139 2 4 10 18 34 56 94 146 228 340 506 3 7 18 38 74 133 233 385 623 977 1501 4 12 34 74 158 297 550 951 1614 2627 4202 5 19 56 133 297 602 1166 2133 3775 6437 10692 6 30 94 233 550 1166 2382 4551 8424 14953 25835 7 45 146 385 951 2133 4551 9142 17639 32680 58659 8 67 228 623 1614 3775 8424 17639 35492 68356 127443 9 97 340 977 2627 6437 14953 32680 68356 136936 264747 10 139 506 1501 4202 10692 25835 58659 127443 264747 530404 Theorem 6.3. The formula corresponding to that of Theorem 6.2 for m roots of degrees (a1 ,a2,..., am) is given by En k°kCk! E Vi,pii+p2i +-----+Pdi = Ci E 1 c k=1 Vd=1,2, nm=^ a= 1 iPd< v^ where the sum^c is over all partitions 1C12C2 • • • nCn G Pn. Proof. This proof uses the same arguments as for Theorem 6.2. □ Using the formula from Theorem 6.3 for the calculations, we present in Table 6 the maximum number of imbedding-types for triply rooted graphs with root-vertices of valences 1 < i,j,k < 5. 1Pd1 2Pd2 ...ad £Pad 292 Ars Math. Contemp. 15 (2018) 441-466 Table 6: The maximum number of imbedding-types for three roots, of valences i, j, k for i = 1, 2,3,4,5. i = 1 i=2 i=3 i=4 i=5 j\k 1 2 3 4 5 1 6 14 28 52 90 2 14 38 84 170 316 3 28 84 206 450 899 4 52 170 450 1058 2254 5 90 316 899 2254 5110 j\k 1 2 3 45 1 14 38 84 170 316 2 38 120 290 644 1284 3 84 290 788 1886 4074 4 170 644 1886 4868 11214 5 316 1284 4074 11214 27556 j\k 1 2 3 45 1 28 84 206 450 899 2 84 290 788 1886 4074 3 206 788 2370 6146 14302 4 450 1886 6146 17170 42696 5 899 4074 14302 42696 112966 j\k 1 2 3 45 1 52 170 450 1058 2254 2 170 644 1886 4868 11214 3 450 1886 6146 17170 42696 4 1058 4868 17170 51630 137070 5 2254 11214 42696 137070 387146 j\k 1 2 3 45 1 90 316 899 2254 5110 2 316 1284 4074 11214 27556 3 899 4074 14302 42696 112966 4 2254 11214 42696 137070 387146 5 5110 27556 112966 387146 1161498 J. L. Gross et al.: Calculating genus polynomials via string operations and matrices 293 7 Conclusions We have focused here primarily on the computational aspects involved in applying string operations toward the determination of genus polynomials of graphs. We recognize the following two immediate benefits of the string-operations paradigm: 1. It enables us to reduce the number of partial genus polynomials (one for each imbed-ding-type) into which a genus polynomial must be partitioned. 2. The imbedding-types, the production matrix, and the partial genus polynomials (which are the coordinates of a pgd-vector) can be calculated by a computer program, which enables us to generate a much larger set of experimental data. Beyond using string operations in new calculations of enumerative results on graph imbeddings, some new theoretical insights may arise from them. One may reasonably consider how the paradigm of string operations relates to the log-concavity conjecture, that every genus polynomial is log-concave (see [16,18]). We observe that using Theorem 4.7.2 of [29] could give generating functions for the individual entries of a power of a production matrix. In a sequel [15], we regard a linear family of graphs as a Markov process is which the states are i-types and a slightly modified form of the production matrix is the transition matrix. We explore the properties of such Markov processes. The methods described here seem amenable to extension. Suppose that instead of a fixed production matrix M(z) for a graph sequence {Gn : n = 0,1,...}, with pgd-vectors Vn(z) we had a sequence of production matrices Mn(z), such that Recursion (4.1) was generalized to Mn(z)Vn(z) = Vn+l(z), and Equation (4.2) to Vn(z) = Mn-l(z)Mn-2(z) • • • Mq(z)Vq(z). A tractable recursion or a closed formula for Mn(z) would enable us to calculate the pgd-vector Vn(z) reasonably rapidly. Of course, such a sequence of production matrices corresponds to a non-stationary Markov process. References [1] D. Babic, A. Graovac, B. Mohar and T. Pisanski, The matching polynomial of a polygraph, Discrete Appl. Math 15 (1986), 11-24, doi:10.1016/0166-218x(86)90014-4. [2] S. Beyer, M. Chimani, I. Hedtke and M. Kotrbcik, A practical method for the minimum genus of a graph: models and experiments, in: A. V. Goldberg and A. S. Kulikov (eds.), Experimental Algorithms, Springer, volume 9685 of Lecture Notes in Computer Science, pp. 75-88, 2016, doi:10.1007/978-3-319-38851-9_6, proceedings of the 15th International Symposium (SEA 2016) held in St. Petersburg, June 5-8, 2016. [3] B. Bollobas and O. M. Riordan, A polynomial invariant of graphs on orientable surfaces, Proc. London Math. Soc. 83 (2001), 513-531, doi:10.1112/plms/83.3.513. [4] Y. Chen, J. L. Gross, T. Mansour and T. W. Tucker, Recurrences for the genus polynomials of linear sequences of graphs, 2016, manuscript, 26 pages. [5] T. Y. Chow and J. West, Forbidden subsequences and Chebyshev polynomials, Discrete Math. 204 (1999), 119-128, doi:10.1016/s0012-365x(98)00384-7. 294 Ars Math. Contemp. 15 (2018) 441-466 [6] M. L. Furst, J. L. Gross and R. Statman, Genus distributions for two classes of graphs, J. Comb. Theory Ser. B 46 (1989), 22-36, doi:10.1016/0095-8956(89)90004-x. [7] I. M. Gessel and R. P. Stanley, Algebraic enumeration, in: R. L. Graham, M. Grotschel and L. Lovasz (eds.), Handbook of Combinatorics, Volume II, Elsevier, Amsterdam & MIT Press, Cambridge, Massachusetts, pp. 1021-1061, 1995. [8] J. L. Gross, Genus distribution of graph amalgamations: self-pasting at root-vertices, Australas. J. Comb. 49 (2011), 19-38, https://ajc.maths.uq.edu.au/pdf/4 9/ajc_v4 9_ p019.pdf. [9] J. L. Gross, Genus distributions of cubic outerplanar graphs, J. Graph Algorithms Appl. 15 (2011), 295-316, doi:10.7155/jgaa.00227. [10] J. L. Gross, Embeddings of cubic Halin graphs: genus distributions, Ars Math. Contemp. 6 (2013), 37-56, doi:10.26493/1855-3974.217.440. [11] J. L. Gross, Embeddings of graphs of fixed treewidth and bounded degree, Ars Math. Contemp. 7 (2014), 379-403, doi:10.26493/1855-3974.366.dd1. [12] J. L. Gross and M. L. Furst, Hierarchy for imbedding-distribution invariants of a graph, J. Graph Theory 11 (1987), 205-220, doi:10.1002/jgt.3190110211. [13] J. L. Gross, I. F. Khan and M. I. Poshni, Genus distribution of graph amalgamations: pasting at root-vertices, Ars Combin. 94 (2010), 33-53. [14] J. L. Gross, I. F. Khan and M. I. Poshni, Genus distributions for iterated claws, Electron. J. Combin. 21 (2014), #P1.12, http://www.combinatorics.org/ojs/index.php/ eljc/article/view/v21i1p12. [15] J. L. Gross, T. Mansour and T. W. Tucker, Markovian analysis of production matrices for genus polynomials, in preparation. [16] J. L. Gross, T. Mansour, T. W. Tucker and D. G. L. Wang, Log-concavity of combinations of sequences and applications to genus distributions, SIAM J. Discrete Math. 29 (2015), 10021029, doi:10.1137/140978867. [17] J. L. Gross, T. Mansour, T. W. Tucker and D. G. L. Wang, Iterated claws have real-rooted genus polynomials, Ars Math. Contemp. 10 (2016), 255-268, doi:10.26493/1855-3974.538.86e. [18] J. L. Gross, D. P. Robbins and T. W. Tucker, Genus distributions for bouquets of circles, J. Comb. Theory Ser. B 47 (1989), 292-306, doi:10.1016/0095-8956(89)90030-0. [19] J. L. Gross and T. W. Tucker, Topological Graph Theory, Dover Publications, Mineola, New York, 2001, reprint of the 1987 original [Wiley, New York] with a new preface and supplementary bibliography. [20] G. A. Jones and J. Wolfart, Dessins d'enfants on Riemann surfaces, Springer Monographs in Mathematics, Springer, Cham, 2016, doi:10.1007/978-3-319-24711-3. [21] M. V. Kaulgud and V. H. Chitgopkar, Polynomial matrix-method for calculation of n-electron energies for linear conjugated polymers, J. Chem. Soc. Faraday Trans. II 73 (1977), 13851395, doi:10.1039/f29777301385. [22] M. V. Kaulgud and V. H. Chitgopkar, Polynomial matrix method for the calculation of charge densities and bond orders in linear conjugated n-electron systems, J. Chem. Soc. Faraday Trans. II74 (1978), 951-957, doi:10.1039/f29787400951. [23] B. Mohar, Genus distribution of path-like and ring-like graphs, oral presentation at SIAM DM'12 at Halifax, Nova Scotia, June 2012. [24] M. Mulase and M. Penkava, Ribbon graphs, quadratic differentials on Riemann surfaces, and algebraic curves defined over Q*, Asian J. Math. 2 (1998), 875-919, doi:10.4310/ajm.1998.v2. n4.a11. J. L. Gross et al.: Calculating genus polynomials via string operations and matrices 295 [25] M. I. Poshni, I. F. Khan and J. L. Gross, Genus distributions of graphs under edge-amalgamations, Ars Math. Contemp. 3 (2010), 69-86, doi:10.26493/1855-3974.110.6b6. [26] M. I. Poshni, I. F. Khan and J. L. Gross, Genus distributions of graphs under self-edge-amalgamations, Ars Math. Contemp. 5 (2012), 127-148, doi:10.26493/1855-3974.166.63e. [27] S. Stahl, Permutation-partition pairs III: Embedding distributions of linear families of graphs, J. Comb. Theory Ser. B 52 (1991), 191-218, doi:10.1016/0095-8956(91)90062-0. [28] S. Stahl, On the zeros of some genus polynomials, Canad. J. Math. 49 (1997), 617-640, doi: 10.4153/cjm-1997-029-5. [29] R. P. Stanley, Enumerative combinatorics, Volume I, The Wadsworth & Brooks/Cole Mathematics Series, Wadsworth & Brooks/Cole Advanced Books & Software, Monterey, California, 1986, doi:10.1007/978-1-4615-9763-6. [30] C. Thomassen, The genus problem for cubic graphs, J. Comb. Theory Ser. B 69 (1997), 52-58, doi:10.1006/jctb.1996.1721. [31] Wikipedia contributors, Shortlex order — Wikipedia, The Free Encyclopedia, 2015, https: //en.wikipedia.org/wiki/Shortlex_order.