Degree sequence conditions for a graph to be disjoint path coverable. (English) Zbl 1511.05044
Summary: A graph \(G\) is many-to-many \(t\)-disjoint path coverable if there exist \(t\)-disjoint paths between any two disjoint vertex subsets \(X = \{ x_1, x_2, \dots, x_t\}\) and \(Y = \{ y_1, y_2, \dots, y_t\}\) of \(G\) such that the union of these paths covers every vertex of \(G\). In the paper, we first provide two degree sequence sufficient conditions for a graph to be many-to-many \(t\)-disjoint path coverable. We also obtain degree sequence sufficient conditions for a graph to be one-to-many disjoint path coverable and one-to-one disjoint path coverable, which are variants of many-to-many disjoint path coverable graphs. We close the paper with analogous results for bipartite graphs.
MSC:
| 05C07 | Vertex degrees |
| 05C40 | Connectivity |
| 05C45 | Eulerian and Hamiltonian graphs |
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
| 68R10 | Graph theory (including graph drawing) in computer science |
References:
| [1] | Akers, S. B.; Krisnamurthy, B., A group theoretic model for symmetric network, IEEE Trans. Comput., 38, 555-566 (1989) · Zbl 0678.94026 |
| [2] | Amar, D.; Favaron, O.; Mago, P.; Ordaz, O., Biclousre and bistability in a balanced bipartite graph, J. Graph Theory, 20, 513-529 (1995) · Zbl 0838.05096 |
| [3] | Bagga, K. S.; Varma, B. N., Bipartite graphs and degree conditions, (Graph Theory, Combinatorics, Algorithms, and Applications (1991), Siam), 564-573 · Zbl 0812.05037 |
| [4] | Berge, C., Graphs and Hypergraphs (1973), North-Holland: North-Holland Amsterdam · Zbl 0483.05029 |
| [5] | Bondy, J. A., Properties of graphs with constraints on degrees, Studia Sci. Math. Hungar., 473-475 (1969) · Zbl 0184.27702 |
| [6] | Bondy, J. A.; Chvátal, V., A method in graph theorey, Discrete Math., 15, 111-135 (1976) · Zbl 0331.05138 |
| [7] | Bondy, J. A.; Murty, U. S.R., Graph Theory (2008), Springer · Zbl 1134.05001 |
| [8] | Chang, C.-H.; Lin, C.-K.; Huang, H.-M.; Hsu, L.-H., The super laceability of hypercubes, Inform. Process. Lett., 92, 15-21 (2004) · Zbl 1173.68599 |
| [9] | Chartrand, G.; Kapoor, S. F.; Kronk, H. V., A sufficient condition for \(n\)-connectedness of graphs, Mathematika, 15, 51-52 (1965) · Zbl 0175.20703 |
| [10] | Dirac, G. A., Some theorems on abstract graphs, Proc. Lond. Math. Soc., 2, 69-81 (1952) · Zbl 0047.17001 |
| [11] | Hsu, D.-F., On container width and length in graphs, groups, and networks, IEICE Trans. Fundam. Electron. Commun. Comput. Sci. E, 668-680 (1994) |
| [12] | Hsu, L.-H.; Lin, C.-K., Graph Theory and Interconnection Networks (2009), CRC Press, Taylor & Francis Group · Zbl 1168.05002 |
| [13] | Huang, P.-Y.; Hsu, L.-H., The spanning connectivity of the line graphs, Appl. Math. Lett., 24, 1614-1617 (2011) · Zbl 1219.05083 |
| [14] | Li, J.; Li, X.; Cheng, E., Super spanning connectivity of split-star networks, Inform. Process. Lett., 166 (2021) · Zbl 1506.68081 |
| [15] | Lick, D. R., A sufficient condition for Hamiltonian connectedness, J. Combin. Theory Ser. B, 8, 444-445 (1970) · Zbl 0193.24401 |
| [16] | Lim, H.-S.; Kim, H.-C.; Park, J.-H., Ore-type degree conditions for disjoint path covers in simple graphs, Discrete Math., 339, 770-779 (2016) · Zbl 1327.05276 |
| [17] | Lin, C.-K.; Huang, H.-M.; Tan, J. J.M.; Hsu, L.-H., On spanning connected graphs, Discrete Math., 308, 1330-1333 (2008) · Zbl 1134.05045 |
| [18] | Lin, C.-K.; Tan, J. J.M.; Hsu, D. F.; Hsu, L.-H., On the spanning fan-connectivity of graphs, Discrete Appl. Math., 157, 1342-1348 (2009) · Zbl 1183.05045 |
| [19] | Moon, J. W.; Moser, L., On hamiltonian bipartite graphs, Isreal J. Math., 1, 163-165 (1963) · Zbl 0119.38806 |
| [20] | Ntafos, S. C.; Hakimi, S. L., On path cover problems in digraphs and applications to program testing, IEEE Trans. Softw. Eng., 5, 520-529 (1979) · Zbl 0412.68052 |
| [21] | Oh, E.; Chen, J., On strong menger-connectivity of star graphs, Discrete Appl. Math., 129, 499-511 (2003) · Zbl 1032.05076 |
| [22] | Ore, O., Note on Hamilton circuits, Amer. Math. Monthly, 67, 55 (1960) · Zbl 0089.39505 |
| [23] | Ore, O., Hamiltonian connected graphs, J. Math. Pures Appl., 42, 21-27 (1963) · Zbl 0106.37103 |
| [24] | Park, J.-H., A sufficient condition for the unpaired k-disjoint path coverability of interval graphs, J. Supercomput., 3, 1-18 (2021) |
| [25] | Pósa, L., A theorem concerning Hamilton lines, Mayyar Tud. Akad. Mat. Kulató Int. Közl., 7, 225-226 (1962) · Zbl 0114.40003 |
| [26] | Sabir, E.; Meng, J., Sufficient conditions for graphs to be spanning connected, Appl. Math. Comput., 378, Article 125198 pp. (2020) · Zbl 1508.05095 |
| [27] | Sabir, E.; Vumar, E., Spanning connectivity of the power of a graph and Hamiltonian-connected index of a graph, Graphs Combin., 30, 1551-1563 (2014) · Zbl 1306.05138 |
| [28] | Shih, Y.-K.; Kao, S.-S., One-to-one disjoint path covers on \(k\)-ary \(n\)-cubes, Theoret. Comput. Sci., 412, 4513-4530 (2011) · Zbl 1223.68086 |
| [29] | Xiong, W.; Song, S.; Xie, Y.; Zhan, M.; Lai, H.-J., Polynomially determining spanning connectivity of locally connected line graphs, Discrete Appl. Math., 295, 102-111 (2021) · Zbl 1460.05102 |
| [30] | Zhang, B.; Yang, W., On the spanning connectivity of tournaments, Discrete Appl. Math., 239, 218-222 (2018) · Zbl 1382.05028 |
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.
