The 3-path connectivity of the folded hypercube

被引:0
作者
Wang, Yi [1 ]
Cheng, Dongqin [1 ]
机构
[1] Jinan Univ, Coll Informat Sci & Technol, Dept Math, Guangzhou 510632, Peoples R China
关键词
Internally disjoint paths; Folded hypercube; Path; Path connectivity; GENERALIZED; 4-CONNECTIVITY; PATH-CONNECTIVITY; 3-CONNECTIVITY; CYCLES;
D O I
10.1007/s11227-025-07558-3
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
Let G be a connected simple graph with vertex set VG\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$V\left( G \right) $$\end{document} and edge set EG\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$E\left( G \right) $$\end{document}. Let Omega\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Omega $$\end{document} be a subset of VG\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$V\left( G \right) $$\end{document} with at least two vertices. A path containing all vertices of Omega\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Omega $$\end{document} is said to be an Omega- path\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Omega \text{- } \text {path}$$\end{document} of G. Two Omega-\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Omega \text{- }$$\end{document}paths P1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{P}_{1}}$$\end{document} and P2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{P}_{2}}$$\end{document} of G are internally disjoint if EP1 boolean AND EP2=& empty;\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$E\left( {{P}_{1}} \right) \cap E\left( {{P}_{2}} \right) =\varnothing $$\end{document}. For an integer k with k >= 2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k\ge 2$$\end{document}, the k- path- connectivity\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k \text{- } \text {path} \text{- } \text {connectivity}$$\end{document}Pi kG\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\Pi }_{k}}\left( G \right) $$\end{document} is defined as Pi kG=min Pi k Omega Omega subset of VGand Omega=k\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\Pi }_{k}}\left( G \right) =\min \left\{ {{\Pi }_{k}}\left( \Omega \right) \left| \, \Omega \subseteq V\left( G \right) \text { and }\left| \, \Omega \right| =k \right. \right\} $$\end{document}, where Pi k Omega\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${{\Pi }_{k}}\left( \Omega \right) $$\end{document} represents the maximum number of internally disjoint Omega- paths\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Omega \text{- } \text {paths}$$\end{document}. In this paper, we determine the 3- path- connectivity\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$3 \text{- } \text {path} \text{- } \text {connectivity}$$\end{document} of the n- dimensional\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n \text{- } \text {dimensional}$$\end{document} folded hypercubes FQn\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F{{Q}_{n}}$$\end{document} and prove that Pi 3FQn=& LeftFloor;3n+1-14 & RightFloor;for\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Pi _3\left( FQ_n \right) =\lfloor \frac{3\left( n+1 \right) -1}{4} \rfloor \text { for }$$\end{document} all n >= 2. \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n\geqslant 2.$$\end{document}
引用
收藏
页数:25
相关论文
共 23 条
[1]   Average connectivity of minimally 2-connected graphs and average edge-connectivity of minimally 2-edge-connected graphs [J].
Casablanca, Rocio M. ;
Mol, Lucas ;
Oellermann, Ortrud R. .
DISCRETE APPLIED MATHEMATICS, 2021, 289 :233-247
[2]   ALGORITHMS AND PROPERTIES OF A NEW 2-LEVEL NETWORK WITH FOLDED HYPERCUBES AS BASIC MODULES [J].
DUH, DR ;
CHEN, GH ;
FANG, JF .
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 1995, 6 (07) :714-723
[3]   PROPERTIES AND PERFORMANCE OF FOLDED HYPERCUBES [J].
ELAMAWY, A ;
LATIFI, S .
IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 1991, 2 (01) :31-42
[4]   The bipanconnectivity and m-panconnectivity of the folded hypercube [J].
Fang, Jywe-Fei .
THEORETICAL COMPUTER SCIENCE, 2007, 385 (1-3) :286-300
[5]   PATH-CONNECTIVITY IN GRAPHS [J].
HAGER, M .
DISCRETE MATHEMATICS, 1986, 59 (1-2) :53-59
[6]   PENDANT TREE-CONNECTIVITY [J].
HAGER, M .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1985, 38 (02) :179-189
[7]   Every edge lies on cycles of folded hypercubes with a pair of faulty adjacent vertices [J].
Kuo, Che-Nan ;
Cheng, Yu-Huei .
DISCRETE APPLIED MATHEMATICS, 2021, 294 :1-9
[8]   The generalized 3-connectivity of graph products [J].
Li, Hengzhe ;
Ma, Yingbin ;
Yang, Weihua ;
Wang, Yifei .
APPLIED MATHEMATICS AND COMPUTATION, 2017, 295 :77-83
[9]   On Tree-Connectivity and Path-Connectivity of Graphs [J].
Li, Shasha ;
Qin, Zhongmei ;
Tu, Jianhua ;
Yue, Jun .
GRAPHS AND COMBINATORICS, 2021, 37 (06) :2521-2533
[10]   The generalized 3-connectivity of the Mycielskian of a graph [J].
Li, Shasha ;
Zhao, Yan ;
Li, Fengwei ;
Gu, Ruijuan .
APPLIED MATHEMATICS AND COMPUTATION, 2019, 347 (882-890) :882-890