JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2024, Vol. 59 ›› Issue (2): 80-90.doi: 10.6040/j.issn.1671-9352.0.2022.404

Previous Articles     Next Articles

Study on semi-paired k-disjoint path cover of unit interval graphs

Li ZHU(),Peng LI,Aifa WANG   

  1. College of Science, Chongqing University of Technology, Chongqing 400054, China
  • Received:2022-07-28 Online:2024-02-20 Published:2024-02-20

RichHTML

0

PDF (PC)

85

Abstract:

The fault tolerance problem of semi-paired, many to many and k-disjoint path cover (k-DPC) on unit interval graphs is studied. Using the structural characteristics of the path cover and the structural properties of the vertex order of the unit interval graphs, the unit interval graphs with semi-paired 1-DPC and k-DPC properties are characterized. At the same time, we obtain the relevant results of the unit interval graph G: for any vertex set W and any edge set F, G-W passing through F has the semi-paired 1-DPC property if and only if G is (2+r)-connected, where |W|=p, |F|=q, p+q≤r; G-W passing through F has the semi-paired k-DPC property if and only if G is (2k+r-1)-connected, where k≥2. It is shown that the existence of disjoint path covers in graphs is closely related to vertex connectivity and Hamiltonian properties. The research methods and results provide a theoretical basis for further study of the path coverage of interval graphs and other related graphs.

Key words: unit interval graph, semi-paired k-DPC, fault tolerance, path cover

CLC Number: 

  • O157.5

Fig.1

A unit interval graph and its interval representation"

Fig.2

Schematic diagram of π1, πt-HP"

Fig.3

Schematic diagram of π[t-1]+πt-1πt+1+τ"

Fig.4

Schematic diagram of π1πj+τ"

Fig.5

π1, πt-HP pass through F"

Fig.6

There is no s1, t1-path in G-π[i0+1, i0+2k-2]"

Fig.7

Schematic diagram of {P1, P2}"

Fig.8

Semi-paired k-DPC"

Fig.9

Schematic diagram of {π[s2-1]+πs2-1πj+P1, P2, P3, …, Pk}"

Fig.10

Schematic diagram of {π[s2-1]+πs2-1πt1, P2}"

Fig.11

Schematic diagram of {π[s2-1]+πs2-1πt1, P2, P3, …, Pk}"

Fig.12

Schematic diagram of {π1π2+P1, P2, P3, …, Pk}"

Fig.13

Schematic diagram of {π1πj+P1, P2, P3, …, Pk}"

Fig.14

Schematic diagram of {Q, P2, P3, …, Pk}"

Fig.15

Schematic diagram of {P1, P2, …, Pk}"

Fig.16

Schematic diagram of {π1π2, P2}"

Fig.17

Schematic diagram of {π1π2, P2, P3, …, Pk}"

Fig.18

Semi-paired k-DPC pass through F"

Fig.19

Schematic diagram of {π1πi, P2}"

Fig.20

Schematic diagram of {π1πi, P2, P3, …, Pk}"

Fig.21

Schematic diagram of {π1πi+πiπ2+P1, P2, P3, …, Pk}"

Fig.22

Path cover {Q, P2, P3, …, Pk}"

Fig.23

Schematic diagram of {π1πi+P1, P2, P3, …, Pk}"

1 WANG Fan , ZHAO Weisheng . One-to-one disjoint path covers in hypercubes with faulty edges[J]. The Journal of Supercomputing, 2019, 75 (8): 5583- 5595.
doi: 10.1007/s11227-019-02817-6
2 DUSART J , CORNEIL D G , HABIB M . Corrigendum: LDFS-based certifying algorithm for the minimum path cover problem on cocomparability graphs[J]. SIAM Journal on Computing, 2021, 50 (3): 1148- 1153.
doi: 10.1137/20M1327835
3 PARK J H , CHOI J , LIM H S . Algorithms for finding disjoint path covers in unit interval graphs[J]. Discrete Applied Mathematics, 2016, 205, 132- 149.
doi: 10.1016/j.dam.2015.12.002
4 CHEN Xiaodong , LIU Mingda , LIU Huiqing . Minimum path cover in quasi-claw-free graphs[J]. Bulletin of the Iranian Mathematical Society, 2020, 46 (3): 815- 820.
doi: 10.1007/s41980-019-00294-4
5 YU Wei , LIU Zhaohui . Better approximability results for min-max tree/cycle/path cover problems[J]. Journal of Combinatorial Optimization, 2019, 37 (2): 563- 578.
doi: 10.1007/s10878-018-0268-8
6 GURSKI F , KOMANDER D , REHS C , et al. Computing directed Steiner path covers[J]. Journal of Combinatorial Optimization, 2022, 43 (2): 402- 431.
doi: 10.1007/s10878-021-00781-7
7 LI Jing , WANG Guoren , CHEN Lichao . Paired 2-disjoint path covers of multi-dimensional torus networks with 2n-3 faulty edges[J]. Theoretical Computer Science, 2017, 677, 1- 11.
doi: 10.1016/j.tcs.2017.03.008
8 LI J , MELEKIAN C , ZUO S R , et al. Unpaired many-to-many disjoint path covers on bipartite k-ary n-cube networks with faulty elements[J]. International Journal of Foundations of Computer Science, 2020, 31 (3): 371- 383.
doi: 10.1142/S0129054120500148
9 PARK J H . Paired many-to-many 3-disjoint path covers in bipartite toroidal grids[J]. Journal of Computing Science and Engineering, 2018, 12 (3): 115- 126.
doi: 10.5626/JCSE.2018.12.3.115
10 PARK J H , IHM I . A linear-time algorithm for finding a one-to-many 3-disjoint path cover in the cube of a connected graph[J]. Information Processing Letters, 2019, 142 (2): 57- 63.
11 ĆUSTIĆ A , LENDL S . The Steiner cycle and path cover problem on interval graphs[J]. Journal of Combinatorial Optimization, 2022, 43 (1): 226- 234.
doi: 10.1007/s10878-021-00757-7
12 CHEN Yong , CAI Yinhui , LIU Longcheng , et al. Path cover with minimum nontrivial paths and its application in two-machine flow-shop scheduling with a conflict graph[J]. Journal of Combinatorial Optimization, 2022, 43 (3): 571- 588.
doi: 10.1007/s10878-021-00793-3
13 KAVRA R , GUPTA A , KANSAL S . Interval graph based energy efficient routing scheme for a connected topology in wireless sensor networks[J]. Wireless Networks, 2021, 27 (8): 5085- 5104.
doi: 10.1007/s11276-021-02782-0
14 PATEL Y S , BAHETI A , MISRA R . Interval graph multi-coloring-based resource reservation for energy-efficient containerized cloud data centers[J]. The Journal of Supercomputing, 2021, 77 (5): 4484- 4532.
doi: 10.1007/s11227-020-03439-z
15 AVANI V S , SHAILA S G , VADIVEL A . Interval graph of facial regions with common intersection salient points for identifying and classifying facial expression[J]. Multimedia Tools and Applications, 2021, 80 (3): 3367- 3390.
doi: 10.1007/s11042-020-09806-5
16 LI Xingfu , FENG Haodi , JIANG Haotao , et al. Solving the maximum internal spanning tree problem on interval graphs in polynomial time[J]. Theoretical Computer Science, 2018, 734, 32- 37.
doi: 10.1016/j.tcs.2017.09.017
17 PRADHAN D , PAL S . An O(n+m) time algorithm for computing a minimum semitotal dominating set in an interval graph[J]. Journal of Applied Mathematics and Computing, 2021, 66 (1): 733- 747.
18 KRATOCHVÍL J , MAS$\mathop {\rm{R}}\limits^{\smile}$ÍK T , NOVOTNÁ J . U-bubble model for mixed unit interval graphs and its applications: the maxcut problem revisited[J]. Algorithmica, 2021, 83 (12): 3649- 3680.
doi: 10.1007/s00453-021-00837-4
19 PARK J H , KIM J H , LIM H S . Disjoint path covers joining prescribed source and sink sets in interval graphs[J]. Theoretical Computer Science, 2019, 776, 125- 137.
doi: 10.1016/j.tcs.2019.01.019
20 PARK J H , LIM H S . Characterization of interval graphs that are unpaired 2-disjoint path coverable[J]. Theoretical Computer Science, 2020, 821, 71- 86.
doi: 10.1016/j.tcs.2020.03.010
21 PARK J H . A sufficient condition for the unpaired k-disjoint path coverability of interval graphs[J]. The Journal of Supercomputing, 2021, 77 (7): 6871- 6888.
doi: 10.1007/s11227-020-03512-7
22 LI Peng , WU Yaokun . A linear time algorithm for the 1-fixed-endpoint path cover problem on interval graphs[J]. SIAM Journal on Discrete Mathematics, 2017, 31 (1): 210- 239.
doi: 10.1137/140981265
23 LOOGES P J , OLARIU S . Optimal greedy algorithms for indifference graphs[J]. Computers & Mathematics with Applications, 1993, 25 (7): 15- 25.
24 CHEN C , CHANG C C , CHANG G J . Proper interval graphs and the guard problem[J]. Discrete Mathematics, 1997, 170 (1/2/3): 223- 230.
[1] ZHONG Yuan, XIONG Shuang, ZHANG Cui-hua, CHEN Hui-jie. Research on fault tolerance strategies of quality improvement in supply chains with market pricing constraints [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2017, 52(6): 10-15.
[2] LUO Jin-mei, ZUO Lian-cui*. On the island sequences of L(2,1)-labeling of graphs [J]. J4, 2011, 46(6): 49-52.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] WANG Bing . Properties of a quasi-claw-free graph[J]. J4, 2007, 42(10): 111 -113 .
[2] ZHU yan,HOU Jian-feng,WANG Ji-hui . [J]. J4, 2006, 41(5): 59 -62 .
[3] JIANG Xue-lian, SHI Hong-bo*. The learning algorithm of a generative and discriminative combination classifier[J]. J4, 2010, 45(7): 7 -12 .
[4] PENG Yan-fen,LI Bao-zong,LIU Tian-bao . Relationships between the structures and the anesthetic[J]. J4, 2006, 41(5): 148 -150 .
[5] . [J]. J4, 2009, 44(3): 84 -87 .
[6] GUO Lei,YU Rui-lin and TIAN Fa-zhong . Optimal control of one kind general jump transition systems[J]. J4, 2006, 41(1): 35 -40 .
[7] DIAO Ke-feng and ZHAO Ping . On the coloring of C-hypergraphs with minimum connected pair graphs[J]. J4, 2007, 42(2): 56 -58 .
[8] XUE Yan-Bei, YANG Bei, CHEN Zhen-Xiang. Structural health monitoring of civil engineering based on wavelet analysis[J]. J4, 2009, 44(9): 28 -31 .
[9] SUN Shou-bin,MENG Guang-wu ,ZHAO Feng . Dα-Continuity of order homomorphism[J]. J4, 2007, 42(7): 49 -53 .
[10] GUO Ting,BAO Xiao-ming . Influences of sitedirected mutagenesis on the enzymeactivity and thethermostability of the xylose isomerase from Thermus thermphilus[J]. J4, 2006, 41(6): 145 -148 .
Copyright 2018 © Editorial office of JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)
Supported by Beijing Magtech Co.Ltd