On the path partition of graphs. (English) Zbl 1521.05161
Let \(G\) be a finite, simple, and undirected graph with vertex set \(V(G)\) and edge set \(E(G)\). Also, we denote the order of \(G\) by \(n\), the minimum degree of the graph \(G\) by \(\delta(G)\), and the maximum degree by \(\Delta(G)\).
A path cover of a graph is a set \(\mathcal{C}\) of paths of the graph such that each vertex belongs to at least one path of \(\mathcal{C}\). The main subject of this paper is related to the path partition problem. A family \(\mathcal{P}\) of paths is called a path partition of a graph \(G\) if its members cover the vertices of the graph and are vertex disjoint. Furthermore, the path partition number of \(G\) is \(\mu(G) = \min\{|\mathcal{P}|:\mathcal{P} \text{~ is a path partition of~} G\}.\) This definition has been stated by Ø. Ore [Ann. Mat. Pura Appl. (4) 55, 315–321 (1961; Zbl 0103.39702)]. In order to find an upper bound for \(\mu(G)\), B. Reed [Comb. Probab. Comput. 5, No. 3, 277–295 (1996; Zbl 0857.05052)] proved that if \(G\) is a connected cubic graph on \(n\) vertices, then \(\mu(G) \leq \lceil\frac{n}{9}\rceil\). After that, G. Yu [J. Graph Theory 88, No. 3, 385–401 (2018; Zbl 1393.05218)] showed that if \(G\) is a \(2\)-connected cubic graph on \(n\) vertices, then \(\mu(G) \leq \lceil\frac{n}{10}\rceil\). Next, C. Magnant and D. M. Martin [Australas. J. Comb. 43, 211–217 (2009; Zbl 1218.05142)] conjectured that if \(G\) is a \(d\)-regular graph on \(n\) vertices, then \(\mu(G) \leq \frac{n}{d+1}\). C. Magnant et al. [Australas. J. Comb. 64, Part 2, 334–340 (2016; Zbl 1333.05243)] extended the conjecture above such that if \(G\) is a graph on \(n\) vertices, then \(\mu(G) \leq \max\left\lbrace\frac{n}{\delta +1}, \frac{(\Delta - \delta)n}{\Delta + \delta}\right\rbrace{.}\) The main aim of this paper is to provide a positive answer to this conjecture for \(\Delta \geq 2\delta\). In fact, the authors show the following theorem:
Theorem. Let \(G\) be a graph of order \(n\) of minimum degree \(\delta\), \((\delta \geq 2),\) and maximum degree \(\Delta\) with \(\Delta \geq 2\delta\). Then \(\mu(G) \leq \frac{(\Delta - \delta)n}{\Delta + \delta}\).
A path cover of a graph is a set \(\mathcal{C}\) of paths of the graph such that each vertex belongs to at least one path of \(\mathcal{C}\). The main subject of this paper is related to the path partition problem. A family \(\mathcal{P}\) of paths is called a path partition of a graph \(G\) if its members cover the vertices of the graph and are vertex disjoint. Furthermore, the path partition number of \(G\) is \(\mu(G) = \min\{|\mathcal{P}|:\mathcal{P} \text{~ is a path partition of~} G\}.\) This definition has been stated by Ø. Ore [Ann. Mat. Pura Appl. (4) 55, 315–321 (1961; Zbl 0103.39702)]. In order to find an upper bound for \(\mu(G)\), B. Reed [Comb. Probab. Comput. 5, No. 3, 277–295 (1996; Zbl 0857.05052)] proved that if \(G\) is a connected cubic graph on \(n\) vertices, then \(\mu(G) \leq \lceil\frac{n}{9}\rceil\). After that, G. Yu [J. Graph Theory 88, No. 3, 385–401 (2018; Zbl 1393.05218)] showed that if \(G\) is a \(2\)-connected cubic graph on \(n\) vertices, then \(\mu(G) \leq \lceil\frac{n}{10}\rceil\). Next, C. Magnant and D. M. Martin [Australas. J. Comb. 43, 211–217 (2009; Zbl 1218.05142)] conjectured that if \(G\) is a \(d\)-regular graph on \(n\) vertices, then \(\mu(G) \leq \frac{n}{d+1}\). C. Magnant et al. [Australas. J. Comb. 64, Part 2, 334–340 (2016; Zbl 1333.05243)] extended the conjecture above such that if \(G\) is a graph on \(n\) vertices, then \(\mu(G) \leq \max\left\lbrace\frac{n}{\delta +1}, \frac{(\Delta - \delta)n}{\Delta + \delta}\right\rbrace{.}\) The main aim of this paper is to provide a positive answer to this conjecture for \(\Delta \geq 2\delta\). In fact, the authors show the following theorem:
Theorem. Let \(G\) be a graph of order \(n\) of minimum degree \(\delta\), \((\delta \geq 2),\) and maximum degree \(\Delta\) with \(\Delta \geq 2\delta\). Then \(\mu(G) \leq \frac{(\Delta - \delta)n}{\Delta + \delta}\).
Reviewer: Mehrdad Nasernejad (Lens)
MSC:
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
| 05C38 | Paths and cycles |
| 05C20 | Directed graphs (digraphs), tournaments |
Keywords:
path partition problemReferences:
| [1] | M. Chen, J. Li, L. Wang, L. Zhang, On partitioning simple bipartite graphs in vertex-disjoint paths, Southeast Asian Bull. Math. 31 (2007), no. 2, 225-230. · Zbl 1150.05022 |
| [2] | H. Enomoto, K. Ota, Partitions of a graph into paths with prescribed endvertices and lengths, J. Graph Theory 34 (2000), no. 2, 163-169. · Zbl 0958.05109 |
| [3] | V. Gruslys, S. Letzter, Cycle partitions of regular graphs, arXiv:1808.00851. · Zbl 1511.05195 |
| [4] | J. Han, On vertex-disjoint paths in regular graphs, Electron. J. Combin. 25 (2018), no. 2, #P2.12. · Zbl 1391.05146 |
| [5] | M. Kouider, Neighborhood and covering vertices by cycles, Combinatorica 20 (2000), no. 2, 219-226. · Zbl 0959.05066 |
| [6] | M. Kouider, Covering vertices by cycles, J. Graph Theory 18 (1994), no. 8, 757-776. · Zbl 0816.05046 |
| [7] | M. Kouider, Z. Lonc, Covering cycles and \(k\)-term degree sums, Combinatorica 16 (1996), 407-412. · Zbl 0857.05058 |
| [8] | J. Li, G. Steiner, Partitioning a bipartite graph into vertex-disjoint paths, Ars Combin. 81 (2006), 161-173. · Zbl 1174.05416 |
| [9] | Ch. Lu, Q. Zhou, Path covering number and \(L(2, 1)\)-labeling number of graphs, Discrete Appl. Math. 161 (2013), 2062-2074. · Zbl 1286.05150 |
| [10] | C. Magnant, D.M. Martin, A note on the path cover number of regular graphs, Australas. J. Combin. 43 (2009), 211-217. · Zbl 1218.05142 |
| [11] | C. Magnant, H. Wang, Path partition of almost regular graphs, Australas. J. Combin. 64 (2016), 334-340. · Zbl 1333.05243 |
| [12] | P. Manuel, Revisiting path-type covering and partitioning problems, (2018), hal-01849313. |
| [13] | O. Ore, Arc coverings of graphs, Ann. Mat. Pura Appl. 55 (1961), no. 4, 315-321. · Zbl 0103.39702 |
| [14] | B. Reed, Paths, stars and the number three, Combin. Probab. Comput. 5 (1996), no. 3, 277-295. · Zbl 0857.05052 |
| [15] | G. Yu, Covering 2-connected 3-regular graphs by disjoint paths, J. Graph Theory 18 (2018), no. 3, 385-401. · Zbl 1393.05218 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
