Edge disjoint caterpillar realizations

DOI10.1016/J.DAM.2020.11.006MaRDI QIDQ2217488zbMATH OpenOpenAlexFDO

Authors István Miklós, Geneva Schlafly, Yuheng Wang, Zhangyang Wei

Publication date 29 December 2020

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

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

zbMATH Keywords

degree sequencesedge disjoint realizationsHamiltonian paths

Mathematics Subject Classification ID

Trees (05C05) Vertex degrees (05C07) Coloring of graphs and hypergraphs (05C15) Enumeration in graph theory (05C30) Eulerian and Hamiltonian graphs (05C45) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Abstract: In this paper, we consider the edge disjoint caterpillar realizations of tree degree sequences. We give the necessary and sufficient conditions when two tree degree sequences have edge disjoint caterpillar realizations. We conjecture that an arbitrary number of tree degree sequences have edge disjoint realizations if every vertex is a leaf in at most one tree. We prove that the conjecture is true if the number of tree degree sequences is at most $4$. We also prove that the conjecture is true if $ngemax22k-11,396$, where $n$ is the number of vertices and $k$ is the number of tree degree sequences.

Recommendations

• Packing tree degree sequences
• A note on caterpillar-embeddings with no two parallel edges
• Degree sequences and graphs with disjoint spanning trees
• scientific article; zbMATH DE number 1155352
• Multigraphic degree sequences and supereulerian graphs, disjoint spanning trees

Cites work

• Advances in discrete tomography and its applications. Some papers based on the presentations at the workshop on discrete tomography and its applications, New York, NY, USA, June 13--15, 2005.
• Colour degree matrices of graphs with at most one cycle
• Degree-constrained edge partitioning in graphs arising from discrete tomography
• Discrete tomography. Foundations, algorithms, and applications
• Disjoint Representation of Three Tree Realizable Sequences. I
• Disjoint Representation of Tree Realizable Sequences
• scientific article; zbMATH DE number 3169205 (Why is no real title available?)
• Note on Hamilton Circuits
• Packing tree degree sequences
• The hidden algorithm of Ore's theorem on Hamiltonian cycles
• The wonderful Walecki construction

Cited in

(2)

• scientific article; zbMATH DE number 1155352 (Why is no real title available?)
• Dense, irregular, yet always-graphic 3-uniform hypergraph degree sequences

This page was built for publication: Edge disjoint caterpillar realizations

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