Paired 2-disjoint path covers of burnt pancake graphs with faulty elements (2024)

Skip Abstract Section

1. [1] Blancoa S., Buehrle C., Patidar A., Cycles in the burnt pancake graph, Discrete Appl. Math. 271 (2019) 1–14. doi:10.1016/j.dam.2019.08.008.Google Scholar
2. [2] Chin C., Weng T.-H., Hsu L.-H., Chiou S.-C., The spanning connectivity of the burnt pancake graphs, IEICE Trans. Inf. Syst. E 92-D (2009) 389–400. doi:10.1587/transinf.E92.D.389.Google Scholar
3. [3] Compeau P.E.C., Girth of pancake graphs, Discrete Appl. Math. 159 (2011) 1641–1645. doi:10.1016/j.dam.2011.06.013.Google Scholar
4. [4] Dvořák T., Gregor P., Partitions of faulty hypercubes into paths with prescribed endvertices, SIAM J. Discrete Math. 22 (2008) 1448–1461. doi:10.1137/060678476.Google Scholar
5. [5] Dvořák T., Gregor P., Koubek V., Generalized Gray codes with prescribed ends, Theor. Comput. Sci. 668 (2017) 70–94. doi:10.1016/j.tcs.2017.01.010.Google Scholar
6. [6] Dvořák T.; Gu M.-M. (2023): Paired 2-disjoint path covers of the 3-dimensional burnt pancake graph. Mendeley Data, V1 doi:10.17632/dg256vjs6x.1.Google Scholar
7. [7] Enomoto H., Ota K., Partitions of a graph into paths with prescribed endvertices and lengths, J. Graph Theory 34 (2000) 163–169. doi:10.1002/1097-0118(200006)34:2<163::AID-JGT5>3.0.CO;2-K.Google Scholar
8. [8] Gates W.H., Papadimitriou C.H., Bounds for sorting by prefix reversal, Discrete Math. 27 (1979) 47–49. doi:10.1016/0012-365X(79)90068-2.Google ScholarDigital Library
9. [9] Gu M.-M., Hao R.-X., Tang S.-M., Chang J.-M., Analysis on component connectivity of bubble-sort star graphs and burnt pancake graphs, Discrete Appl. Math. 279 (2020) 80–91. doi:10.1016/j.dam.2019.10.018.Google Scholar
10. [10] Gu M.-M., Chang J.-M., Neighbor connectivity of pancake graphs and burnt pancake graphs, Discrete Appl. Math. 324 (2022) 46–57. doi:10.1016/j.dam.2022.09.013.Google Scholar
11. [11] Iwasaki T., Kaneko K., Fault-tolerant routing in burnt pancake graphs, Inf. Process. Lett. 110 (2010) 535–538. doi:10.1016/j.ipl.2010.04.023.Google Scholar
12. [12] Hu X., Liu H., The (conditional) matching preclusion for burnt pancake graphs, Discrete Appl. Math. 161 (2013) 1481–1489. doi:10.1016/j.dam.2013.01.010.Google Scholar
13. [13] Kaneko K., Hamiltonian cycles and Hamiltonian paths in faulty burnt pancake graphs, IEICE Trans. Inf. Syst. E 90-D (4) (2007) 716–721. doi:10.1093/ietisy/e90-d.4.716.Google Scholar
14. [14] Kim S.-Y., Park J.-H., Paired many-to-many disjoint path covers in recursive circulants G ( 2 m , 4 ) , IEEE Trans. Comput. 62 (12) (2013) 2468–2475. doi:10.1109/TC.2012.133.Google Scholar
15. [15] Lovász L., Combinatorial Problems and Exercises, North Holland, Amsterdam, 1993, doi:10.1016/C2009-0-09109-0.Google Scholar
16. [16] Park J.-H., Unpaired many-to-many disjoint path covers in nonbipartite torus-like graphs with faulty elements, IEEE Access 10 (2022) 127589–127600. doi:10.1109/ACCESS.2022.3226687.Google Scholar
17. [17] Park J.-H., Ihm I., Many-to-many two-disjoint path covers in cylindrical and toroidal grids, Discrete Appl. Math. 185 (2015) 168–191. doi:10.1016/j.dam.2014.12.008.Google Scholar
18. [18] Park J.-H., Kim H.-C., Lim H.-S., Many-to-many disjoint path covers in hypercube-like interconnection networks with faulty elements, IEEE Trans. Parallel Distrib. Syst. 17 (3) (2006) 227–240. doi:10.1109/TPDS.2006.37.Google Scholar
19. [19] Park J.-H., Lim H.-S., Characterization of interval graphs that are paired 2-disjoint path coverable, J. Supercomput. (2022) doi:10.1007/s11227-022-04768-x.Google Scholar
20. [20] Song S., Li X., Zhou S., Chen M., Fault tolerance and diagnosability of burnt pancake networks under the comparison model, Theor. Comput. Sci. 582 (2015) 48–59. doi:10.1016/j.tcs.2015.03.027.Google Scholar
21. [21] Song S., Zhou S., Li X., Conditional diagnosability of burnt pancake networks under the PMC model, Comput. J. 59 (1) (2016) 91–105. doi:10.1093/comjnl/bxv066.Google Scholar

• Paired many-to-many disjoint path covers in faulty hypercubes

  A paired many-to-many k-disjoint path cover (k-DPC for short) of a graph is a set of k disjoint paths joining k distinct source-sink pairs that cover all the vertices of the graph. Extending the notion of DPC, we define a paired many-to-many bipartite k-...

  Read More

• Paired many-to-many disjoint path covers of hypercubes with faulty edges

  Let M"k={u"i,v"i}"i"="1^k be a set of k pairs of distinct vertices of the n-dimensional hypercube Q"n such that it contains k vertices from each class of bipartition of Q"n. Gregor and Dvorak proved that if n>2k, then there exist k vertex-disjoint paths ...

  Read More

• A linear-time algorithm for finding a paired 2-disjoint path cover in the cube of a connected graph

  For a connected graph G=(V(G),E(G)) and two disjoint subsets of V(G)A={1,,k} and B={1,,k}, a paired (many-to-many) k-disjoint path cover of G joining A and B is a vertex-disjoint path cover {P1,,Pk} such that Pi is a path from i to i for 1ik. In the ...

  Read More