Leaf realization problem, caterpillar graphs and prefix normal words

DOI10.1016/j.tcs.2018.04.019zbMath1395.68206arXiv1712.01942OpenAlexW2771270479WikidataQ129743713 ScholiaQ129743713MaRDI QIDQ1637224

Élise Vandomme, Émile Nadeau, Mélodie Lapointe, Alain Goupil, Alexandre Blondin Massé, Julien de Carufel

Publication date: 7 June 2018

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

graph theorycombinatorics on wordsleafprefix normal wordsinduced subtreesprefix normal form

Mathematics Subject Classification ID

Combinatorics on words (68R15) Graph theory (including graph drawing) in computer science (68R10)

Related Items

Saturated fully leafed tree-like polyforms and polycubes, Generating a Gray code for prefix normal words in amortized polylogarithmic time per word, On infinite prefix normal words, The asymptotic number of prefix normal words, Bubble-flip -- a new generation algorithm for prefix normal words

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on the characterization of digraphic sequences
• On prefix normal words and prefix normal forms
• A theorem on flows in networks
• Zero-one matrices with zero trace
• Arbres avec un nombre maximum de sommets pendants
• Words and graphs
• Maximum induced trees in graphs
• On the realization of a (p,s)-digraph with prescribed degrees
• Fully leafed tree-like polyominoes and polycubes
• Algorithms for constructing graphs and digraphs with given valences and factors
• The number of caterpillars
• A remark on the existence of finite graphs
• Combinatorial Properties of Matrices of Zeros and Ones
• The Generalized Regenerator Location Problem
• On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I
• Properties of a Class of (0,1)-Matrices Covering a given Matrix
• On Combinatorial Generation of Prefix Normal Words
• On Prefix Normal Words