On minimal arbitrarily partitionable graphs

DOI10.1016/J.IPL.2012.06.010MaRDI QIDQ456092zbMATHOpenAlexFDO

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

Publication date 23 October 2012

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2012.06.010

zbMATH Keywords

interconnection networksarbitrary vertex decomposable graphminimal arbitrarily partitionable graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Some properties of minimal arbitrarily partitionable graphs
• scientific article; zbMATH DE number 1792660
• On the structure of arbitrarily partitionable graphs with given connectivity
• Graph partitions with minimum degree constraints
• scientific article; zbMATH DE number 4021173
• Partitions of multigraphs under minimum degree constraints
• scientific article; zbMATH DE number 3867385
• On partition graphs
• scientific article; zbMATH DE number 3506748
• On partitional and other related 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
• Decomposable trees: A polynomial algorithm for tripodes
• Decomposing trees with large diameter
• On arbitrarily vertex decomposable trees
• On the shape of decomposable trees
• On the structure of arbitrarily partitionable graphs with given connectivity

Cited in

(21)

• More aspects of arbitrarily partitionable graphs
• Partitioning powers of traceable or Hamiltonian graphs
• About skew partitions in minimal imperfect graphs
• Some properties of minimal arbitrarily partitionable graphs
• Arbitrarily partitionable \(\{2K_2, C_4\}\)-free graphs
• On smallest regular graphs with a given isopart
• Dense arbitrarily partitionable graphs
• Partitioning Harary graphs into connected subgraphs containing prescribed vertices
• On the longest path in a recursively partitionable graph
• Dense on-line arbitrarily partitionable graphs
• Arbitrarily edge-partitionable graphs
• Problème de la bipartition minimale d'un graphe
• Interplays between variations of arbitrarily partitionable graphs under minimality constraints
• scientific article; zbMATH DE number 5907542 (Why is no real title available?)
• Small dense on-line arbitrarily partitionable graphs
• Partitioning the Cartesian product of a tree and a cycle
• A minimal surface criterion for graph partitioning
• Minimum flow number of complete multipartite graphs
• Min-Max Graph Partitioning and Small Set Expansion
• On the structure of arbitrarily partitionable graphs with given connectivity
• scientific article; zbMATH DE number 4081587 (Why is no real title available?)

This page was built for publication: On minimal arbitrarily partitionable graphs

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