Partitioning powers of traceable or Hamiltonian graphs

DOI10.1016/J.TCS.2013.10.016MaRDI QIDQ391776zbMATH OpenOpenAlexFDO

Authors Olivier Baudon, Julien Bensmail, Jakub Przybyło, Mariusz Woźniak

Publication date 13 January 2014

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

Full work available at URL https://doi.org/10.1016/j.tcs.2013.10.016

zbMATH Keywords

power of a graphHamiltonian grapharbitrarily partitionable graphtraceable graph

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• More aspects of arbitrarily partitionable graphs
• scientific article; zbMATH DE number 6291271
• On minimal arbitrarily partitionable graphs
• Partitioning Harary graphs into connected subgraphs containing prescribed vertices
• Dense arbitrarily partitionable graphs

Cites work

• scientific article; zbMATH DE number 3603293 (Why is no real title available?)
• A degree bound on decomposable trees
• A homology theory for spanning tress of a graph
• A linear algorithm for bipartition of biconnected graphs
• A linear-time algorithm for four-partitioning four-connected planar graphs
• Arbitrarily vertex decomposable caterpillars with four or five leaves
• Arbitrarily vertex decomposable trees are of maximum degree at most six
• Decomposable trees: A polynomial algorithm for tripodes
• Decomposing trees with large diameter
• Decomposition of Complete Bipartite Even Graphs into Closed Trails
• Dense arbitrarily vertex decomposable graphs
• On arbitrarily vertex decomposable trees
• Packing closed trails into dense graphs.
• Recursively arbitrarily vertex-decomposable suns

Cited in

(9)

• Partitioning the Cartesian product of a tree and a cycle
• Arbitrarily partitionable \(\{2K_2, C_4\}\)-free graphs
• Dense on-line arbitrarily partitionable graphs
• On three polynomial kernels of sequences for arbitrarily partitionable graphs
• Arbitrary partitionability of product graphs
• Closure results for arbitrarily partitionable graphs
• Dense arbitrarily partitionable graphs
• On the complexity of partitioning a graph into a few connected subgraphs
• Some properties of minimal arbitrarily partitionable graphs

This page was built for publication: Partitioning powers of traceable or Hamiltonian graphs

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