Partitioning powers of traceable or Hamiltonian graphs

DOI10.1016/J.TCS.2013.10.016zbMATH Open1305.05185OpenAlexW1965792160MaRDI QIDQ391776FDOQ391776

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

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

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)

Cites Work

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

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)