Euler-genus distributions of cubic caterpillar-Halin graphs

DOI10.1007/S40840-021-01084-0zbMATH Open1470.05046arXiv1903.07060OpenAlexW3126568877MaRDI QIDQ2045288FDOQ2045288

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)

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.

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

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

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)

Cites Work

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

Cited In (6)

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

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)