Euler-genus distributions of cubic caterpillar-Halin graphs

DOI10.1007/S40840-021-01084-0MaRDI QIDQ2045288zbMATH OpenOpenAlexFDO

Authors Jinlian Zhang, Qiyao Chen, Xuhui Peng

Publication date 12 August 2021

Published in Bulletin of the Malaysian Mathematical Sciences Society. Second Series (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1903.07060

zbMATH Keywords

overlap matrixembedding distributioncubic Halin graphEuler-genus polynomial

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph polynomials (05C31) Planar graphs; geometric and topological aspects of graph theory (05C10)

Abstract: Gross derived an $O(n^2)$-time algorithm to calculate the genus distribution of a given cubic Halin graph. In this paper, with the help of overlap matrix, we get a recurrence relation for the Euler-genus polynomial of cubic caterpillar-Halin graphs. Explicit formulas for the embeddings of cubic caterpillar-Halin graph into a surface with Euler-genus 0, 1 and 2 are also obtained.

Recommendations

• Embeddings of cubic Halin graphs: genus distributions
• Genus distributions of cubic caterpillar-Halin graphs.
• Recursive formulas for embedding distributions of cubic outerplanar graphs
• Genus distributions of cubic series-parallel graphs
• Log-concavity of the genus polynomials for a sequence of cubic Halin graphs

Cites work

• An Euler-genus approach to the calculation of the crosscap-number polynomial
• An obstruction to embedding graphs in surfaces
• Calculating genus polynomials via string operations and matrices
• Embedding distributions and Chebyshev polynomials
• Embeddings of 3-connected 3-regular planar graphs on surfaces of non-negative Euler characteristic
• Embeddings of cubic Halin graphs: genus distributions
• Genus distributions of 4-regular outerplanar graphs
• Orientable embedding genus distribution for certain types of graphs
• Permutation-partition pairs. III: Embedding distributions of linear families of graphs
• Quadrangular embeddings of complete graphs and the even map color theorem
• The genus distributions of 4-regular digraphs
• Total embedding distributions of Ringel ladders

Cited in

(6)

• Partial-dual Euler-genus distributions for bouquets with small Euler genus
• Genus distributions of cubic caterpillar-Halin graphs.
• Recursive formulas for embedding distributions of cubic outerplanar graphs
• Embeddings of cubic Halin graphs: genus distributions
• Genus distributions of cubic series-parallel graphs
• Log-concavity of the genus polynomials for a sequence of cubic Halin graphs

This page was built for publication: Euler-genus distributions of cubic caterpillar-Halin graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2045288)