English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

A Halin graph is a graph obtained from a plane tree by running a cycle through its leaf vertices in the order they are encountered along a counterclockwise pre-order traversal. Using a vectorized production matrix, we give a matrix formula for the partitioned genus polynomial of any cubic Halin graph and for the genus polynomial as well. We prove log-concavity of the genus polynomial and of the partitioned genus polynomials for several sequences of cubic Halin graphs, which serves as further support of the conjecture that the genus polynomial of every graph is logconcave. Our general concern is enumerating all possible cellular imbeddings f : G→ S of a given graph G in an oriented surface S. An imbedding is cellular if the interior of every face (component of S − f(G)) is homeomorphic to an open disk. Two imbeddings f : G → S and g : G → S are regarded as the same if there is an orientation-preserving homeomorphism of the surface S taking f(G) to g(G) that induces the identity automorphism of G. Our enumeration of imbeddings is according to the genus of the imbedding surface. We define the genus distribution of a finite graph G to be the sequence 〈gi(G) | i = 0, 1, 2, . . .〉 where gi(G) counts the cellular imbeddings of G in the closed orientable surface Si of genus i. The genus polynomial gG(z) of G is the generating function Σgi(G)z . To understand the derivation of genus distributions, we must understand how adding an edge to a graph G affects the genus distribution and its properties. Adding an edge between two 2-valent vertices having a common neighbor is one of the simplest versions of this situation. In this paper, we are within a context for this kind of edge-adding in which the graph G to be modified is from a family of known genus distribution. One way of looking at the two other families of Halin graphs, beyond Ringel ladders, for which we derive genus polynomials and prove their log-concavity, is that each of the graphs in these other families is obtained by adding a single edge to a Ringel ladder. Section 1 reviews the quadrangulation of plane cubic Halin graphs, from [Gr13]. Section 2 shows how they fit with the subsequently invented construct [GMT13] called a vectorized production matrix. In Section 3, we prove that the cubic Halin graphs can be counted with Catalan numbers. The genus polynomials of some infinite sequences of Halin graphs are derived in Section 4. They are proved to be log-concave in Section 5. Moreover, we show that the partitioned genus polynomials of the graphs in that sequence are log-concave, which supports a secondary log-concavity conjecture. In Section 6, we give a few research problems concerned with extending these results. Date: December 13, 2013. 1 2 J. L. GROSS, T. MANSOUR, AND T. W. TUCKER 1. Quadrangulation of cubic Halin graphs An algorithm is given by [Gr13] for calculating the genus distribution of a cubic Halin graph G, which is specified as the 1-skeleton of a 2-complex K on the plane disk D bounded by the outer cycle of G. We construe the graph G to be colored black. We give a 3-step process for constructing a 3-colorable quadrangulation of the 2-complex K. Step 1. In each cycle edge of the Halin graph, insert a red midpoint. This is illustrated in Figure 1. Step 2. Join each red vertex v to all of the non-leaf vertices on the boundary of the face on whose boundary v lies, as shown in Figure 2. Figure 1. Halin graph plus red midpoints on the exterior cycle. Figure 2. Halin graph plus all of the red edges. Proposition 1.1. The red and black edges together triangulate the plane disk D bounded by the exterior cycle of a plane Halin graph G. Proof. This is Proposition 3.1 of [Gr13]. Proposition 1.2. Every black tree edge lies on two of the triangles formed by Steps 1 and 2. Proof. This is Proposition 3.2 of [Gr13]. Step 3a. For each black tree edge, we pair the two incident triangles into a quadrangle. Step 3b. We assign (unseen) colors blue, green, and pink to the tree edges, so as to form a proper edge 3-coloring. This is possible because any tree of maximum degree 3 is edge-3-colorable (via greedy algorithm). Step 3c. We visibly color each quadrangle with the unseen color of the tree edge that bisects it, as shown in Figure 3. The graph that results from deleting from a plane Halin graph G all the vertices on the outer cycle and all the edges incident on them is called the inner tree of G. GENUS POLYNOMIALS OF HALIN GRAPHS 3 Figure 3. Quadrangulation of a plane Halin graph. 2. VP-matrix for the π-merge operation In this section, we reinterpret the genus distribution algorithm of [Gr13] for a cubic Halin graph, in terms of a vectorized production matrix (abbr. vp-matrix ), a new construct introduced by [GMT13]. Some familiarity with partitioned genus distributions and productions, which are constructs introduced in [GKP10], [PKG10], [KPG10], and [Gr11a], is assumed. (A completely general version of these constructs is developed in [Gr14].) 2.1. Partials for cubic Halin graphs. For a doubly vertex-rooted cubic Halin graph (G, u, v), with the roots u and v inserted at the midpoints of adjacent edges, we split gi(G) into six partials. Here is what they count: ddi: Each of the roots u and v lies on two distinct fb-walks. One and only one of these fb-walks traverses both roots. dd′′ i : Each of the roots u and v lies on two distinct fb-walks. Both of these fb-walks traverse both roots. dsi: Root u lies on two distinct fb-walks. One of these fb-walks traverses root v twice. sd′: Root v lies on two distinct fb-walks. One of these fb-walks traverses root u twice. ssi : A single fb-walks traverses roots u and v twice. The occurrences of each root are consecutive. ssi : A single fb-walks traverses roots u and v twice. The occurrences of the two roots alternate. These configurations are illustrated in Figure 4. ss1 ss2 sd' ds' dd" dd'

Log-concavity of the genus polynomials for a sequence of cubic Halin graphs