3-path-connectivity of bubble-sort star graphs
The Journal of Supercomputing · 03.01.2026 · 82 (2)
DOI: 10.1007/s11227-025-08176-9 ↗Kurz gefasst
Fachartikel in der Zeitschrift The Journal of Supercomputing, online erschienen am 03.01.2026. Verfasst von Yi-Lu Luo und 2 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 22 Literaturangaben.
Abstract (Originalsprache)
Let G be a simple connected graph with vertex set V(G) and edge set E(G). Let T be a subset of V(G) with cardinality |T|≥2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$|T|\ge 2$$\end{document}. A path connecting all vertices of T is called a T-path of G. Two T-paths Pi\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$P_i$$\end{document} and Pj\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$P_j$$\end{document} are T¯\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\overline{T}$$\end{document}-disjoint if V(Pi)∩V(Pj)=T\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$V(P_i)\cap V(P_j)=T$$\end{document} and E(Pi)∩E(Pj)=∅\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$E(P_i)\cap E(P_j)=\emptyset$$\end{document}. Denote by πG(T)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\pi _G(T)$$\end{document} the maximum number of T¯\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\overline{T}$$\end{document}-disjoint paths in G. For an integer ℓ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\ell$$\end{document} with ℓ≥2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\ell \ge 2$$\end{document}, the ℓ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\ell$$\end{document}-path-connectivity πℓ(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\pi _\ell (G)$$\end{document} of G is formulated as min{πG(T)∣T⊆V(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\min \{\pi _G(T)\mid T\subseteq V(G)$$\end{document} and |T|=ℓ}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$|T|=\ell \}$$\end{document}. In this paper, we study the 3-path-connectivity of the n-dimensional bubble-sort star graph BSn\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$BS_n$$\end{document}. As a promising interconnection network topology for high-performance computing (HPC) systems, BSn\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$BS_n$$\end{document} possesses numerous superior properties. By deeply analyzing its structural characteristics, we show that π3(BSn)=⌊3n2⌋-3\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\pi _3(BS_n)=\lfloor \frac{3n}{2}\rfloor -3$$\end{document} for any n≥3\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n\ge 3$$\end{document}.
Zitieren
APA
Luo, Y., Deng, Y., & Sun, Y. (2026). 3-path-connectivity of bubble-sort star graphs. The Journal of Supercomputing, 82(2). https://doi.org/10.1007/s11227-025-08176-9
Vancouver
Luo Y, Deng Y, Sun Y. 3-path-connectivity of bubble-sort star graphs. The Journal of Supercomputing. 2026;82(2). doi:10.1007/s11227-025-08176-9
BibTeX
@article{Luo2026,
author = {Luo, Yi-Lu and Deng, Yun-Ping and Sun, Yuan},
title = {3-path-connectivity of bubble-sort star graphs},
journal = {The Journal of Supercomputing},
year = {2026},
volume = {82},
number = {2},
doi = {10.1007/s11227-025-08176-9}
}
EUVIMED