Decomposing highly edge-connected graphs into paths of any given length

DOI10.1016/J.JCTB.2016.07.010MaRDI QIDQ345101zbMATH OpenOpenAlexFDO

Authors M. T. I. Oshiro, Yoshiko Wakabayashi, F. Botler, G. O. Mota

Publication date 25 November 2016

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

decompositionconnectivitypath

Mathematics Subject Classification ID

Distance in graphs (05C12) Paths and cycles (05C38) Connectivity (05C40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: In 2006, Bar'at and Thomassen posed the following conjecture: for each tree $T$, there exists a natural number $k_T$ such that, if $G$ is a $k_T$-edge-connected graph and $|E(G)|$ is divisible by $|E(T)|$, then $G$ admits a decomposition into copies of $T$. This conjecture was verified for stars, some bistars, paths of length $3$, $5$, and $2^r$ for every positive integer $r$. We prove that this conjecture holds for paths of any fixed length.

Recommendations

• Decompositions of highly connected graphs into paths of any given length
• Decomposing highly connected graphs into paths of length five
• Decompositions of highly connected graphs into paths of length five
• Decomposing graphs into paths of fixed length
• Decomposing graphs into paths and trees

Cites work

• scientific article; zbMATH DE number 1334640 (Why is no real title available?)
• scientific article; zbMATH DE number 1179517 (Why is no real title available?)
• A Reduction Method for Edge-Connectivity in Graphs
• Claw‐decompositions and tutte‐orientations
• Connected Detachments of Graphs and Generalized Euler Trails
• Connected \((g,f)\)-factors
• Decomposing a graph into bistars
• Decomposing graphs into paths of fixed length
• Decomposing highly connected graphs into paths of length five
• Decomposing regular graphs with prescribed girth into paths of given length
• Decomposing series-parallel graphs into paths of length 3 and triangles
• Decompositions of highly connected graphs into paths of any given length
• Decompositions of highly connected graphs into paths of length 3
• Decompositions of highly connected graphs into paths of length five
• Decompositions of triangle-free 5-regular graphs into paths of length five
• Edge-Disjoint Spanning Trees of Finite Graphs
• Edge-decomposition of graphs into copies of a tree with four edges
• Edge-decompositions of highly connected graphs into paths
• Edge-partitioning a graph into paths: beyond the Barát-Thomassen conjecture
• Factors and factorizations of graphs. Proof techniques in factor theory
• Graph Decomposition is NP-Complete: A Complete Proof of Holyer's Conjecture
• Graph theory
• Nowhere-zero 3-flows and modulo \(k\)-orientations
• On the Problem of Decomposing a Graph into n Connected Factors
• The weak 3-flow conjecture and the weak circular flow conjecture

Cited in

(18)

• Decomposing 8-regular graphs into paths of length 4
• Decomposing highly connected graphs into paths of length five
• Decomposing highly edge-connected graphs into homomorphic copies of a fixed tree
• Cycle decompositions in \(k\)-uniform hypergraphs
• Edge-partitioning a graph into paths: beyond the Barát-Thomassen conjecture
• Edge-decomposition of graphs into copies of a tree with four edges
• Hamilton path decompositions of complete multipartite graphs
• Decomposing graphs into paths and trees
• Decomposing regular graphs with prescribed girth into paths of given length
• Edge-decompositions of highly connected graphs into paths
• Decomposing graphs into long paths
• Decompositions of highly connected graphs into paths of length 3
• Decompositions of highly connected graphs into paths of any given length
• Decompositions of highly connected graphs into paths of length five
• A proof of the Barát-Thomassen conjecture
• Decomposing a graph into bistars
• Decomposing graphs into paths of fixed length
• Edge‐decomposing graphs into coprime forests

This page was built for publication: Decomposing highly edge-connected graphs into paths of any given length

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