A P₃-decomposition of tournaments and bipartite digraphs

DOI10.1016/J.DAM.2017.04.002MaRDI QIDQ2357785zbMATH OpenOpenAlexFDO

Authors Fangxia Wang, Baoyindureng Wu, Xinhui An

Publication date 14 June 2017

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

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

zbMATH Keywords

bipartite digraphsline graphspath-decompositionperfect matchingstournaments

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph operations (line graphs, products, etc.) (05C76)

Abstract: A $overrightarrow{P}_3$-decomposition of a directed graph $D$ is a partition of the arcs of $D$ into directed paths of length $2$. In this paper, we give a characterization for a tournament and a bipartite digraph admitting a $overrightarrow{P}_3$-decomposition. This solves a problem posed by Diwan ($overrightarrow{P}_3$-decomposition of directed graphs, Discrete Appl. Math., http:// dx.doi.org/10.1016/j.dam.2016.01.039.).

Recommendations

• \(\vec{P_3}\)-decomposition of directed graphs
• Decomposing semi-complete multigraphs and directed graphs into paths of length two
• scientific article; zbMATH DE number 994585
• Path numbers of balanced bipartite tournaments
• Large sets of oriented P₃-decompositions of directed complete bipartite graphs

Cites work

• Characterizations of derived graphs
• Decomposing graphs into paths of fixed length
• Decompositions of highly connected graphs into paths of length 3
• Edge-decompositions of highly connected graphs into paths
• From the theory of regular graphs of third and fourth degree
• Hamiltonian results inK1,3-free graphs
• scientific article; zbMATH DE number 3150485 (Why is no real title available?)
• scientific article; zbMATH DE number 47528 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3013308 (Why is no real title available?)
• On a closure concept in claw-free graphs
• On Representatives of Subsets
• Reflections on graph theory
• The Factorization of Linear Graphs
• The Factors of Graphs

Cited in

(4)

• On the vertices of a 3-partite tournament not in triangles
• Isomorphisms of directed \({\vec{P}}_3\)-graphs.
• Decomposing semi-complete multigraphs and directed graphs into paths of length two
• scientific article; zbMATH DE number 994585 (Why is no real title available?)

This page was built for publication: A \(\vec{P_3}\)-decomposition of tournaments and bipartite digraphs

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