On the path partition of graphs

DOI10.7494/OPMATH.2023.43.6.829MaRDI QIDQ6137690zbMATH OpenOpenAlexFDO

Authors Mekkia Kouider, Mohamed Zamime

Publication date 4 September 2023

Published in Opuscula Mathematica (Search for Journal in Brave)

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

zbMATH Keywords

path partition problem

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: Let $G$ be a graph of order $n$. The maximum and minimum degree of $G$ are denoted by $Delta$ and $delta$ respectively. The emph{path partition number} $mu(G)$ of a graph $G$ is the minimum number of paths needed to partition the vertices of $G$. Magnant, Wang and Yuan conjectured that $mu(G)leqmaxleftfracndelta+1,fracleft(Delta-deltaight)nleft(Delta+deltaight)ight.$ In this work, we give a positive answer to this conjecture, for $Deltageq2delta$.medskip end{abstract}

Recommendations

• Path partitions of almost regular graphs
• The Path Partition Conjecture
• A survey of the path partition conjecture
• An asymptotic result for the path partition conjecture
• On the path partition number of 6‐regular graphs

Cites work

• A note on the path cover number of regular graphs
• Arc coverings of graphs
• Covering 2-connected 3-regular graphs with disjoint paths
• Covering cycles and \(k\)-term degree sums
• Covering vertices by cycles
• Cycle partitions of regular graphs
• Neighborhoods and covering vertices by cycles
• On partitioning simple bipartite graphs in vertex-disjoint paths
• On vertex-disjoint paths in regular graphs
• Partitioning a bipartite graph into vertex-disjoint paths.
• Partitions of a graph into paths with prescribed endvertices and lengths
• Path covering number and \(L(2,1)\)-labeling number of graphs
• Path partitions of almost regular graphs
• Paths, Stars and the Number Three

Cited in

(19)

• Path partitions and packs of acyclic digraphs
• Partitions of digraphs into paths or circuits
• Conditions for graphs to be path partition optimal
• A fast randomized algorithm for partitioning a graph into paths of fixed length
• Partitioning graphs into paths or cycles of prescribed lengths
• Graphs with a path partition for structuring digital spaces
• Path partitions of almost regular graphs
• A survey of the path partition conjecture
• A note on the path cover number of regular graphs
• Path Partitions, Cycle Covers and Integer Decomposition
• scientific article; zbMATH DE number 1786512 (Why is no real title available?)
• scientific article; zbMATH DE number 2152547 (Why is no real title available?)
• Path partitions and forward-only trellis algorithms
• On path partitions of the divisor graph
• The Path Partition Conjecture
• On the path partition number of 6‐regular graphs
• On partitioning the edge set of a graph into internally disjoint paths without exterior vertices
• The path partition conjecture is true for claw-free graphs
• On partitioning simple bipartite graphs in vertex-disjoint paths

This page was built for publication: On the path partition of graphs

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