ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 23 (2023) #P3.04
https://doi.org/10.26493/1855-3974.2913.35e
(Also available at http://amc-journal.eu)
Component (edge) connectivity of
pancake graphs*
Xiaohui Hua † , Lulu Yang
School of Mathematics and Information Science, Henan Normal University, Xinxiang,
Henan 453007, P. R. China
Received 25 June 2022, accepted 17 November 2022, published online 17 January 2023
Abstract
The l-component (edge) connectivity of a graph G, denoted by cκl(G) (cλl(G)), is
the minimum number of vertices (edges) whose removal from G results in a disconnected
graph with at least l components. The pancake graph Pn is a popular underlying topology
for distributed systems. In the paper, we determine the cκl(Pn) and cλl(Pn) for 3 ≤ l ≤ 5.
Keywords: Component connectivity, component edge connectivity, pancake graphs, fault tolerance.
Math. Subj. Class. (2020): 05C40, 05C75
*The authors are grateful to anonymous referees for helpful remarks and suggestions.
†Corresponding author.
E-mail addresses: xhhua@htu.edu.cn (Xiaohui Hua), yllyanglulu@126.com (Lulu Yang)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
ISSN 1855-3966 (tiskana izd.), ISSN 1855-3974 (elektronska izd.)
ARS MATHEMATICA CONTEMPORANEA 23 (2023) #P3.04
https://doi.org/10.26493/1855-3974.2913.35e
(Dostopno tudi na http://amc-journal.eu)
Komponentna (povezavna) povezanost
palačinkastih grafov*
Xiaohui Hua † , Lulu Yang
School of Mathematics and Information Science, Henan Normal University, Xinxiang,
Henan 453007, P. R. China
Prejeto 25. junija 2022, sprejeto 17. novembra 2022, objavljeno na spletu 17. januarja 2023
Povzetek
l-komponentna (povezavna) povezanost grafa G, označena s cκl(G) (cλl(G)), je naj-
manjše število vozlišč (povezav), katerih odstranitev iz grafa G naredi nepovezan graf z
najmanj l komponentami. Palačinkast graf Pn je priljubljena osnovna topologija porazdel-
jenih sistemov. V tem članku določimo cκl(Pn) in cλl(Pn) za 3 ≤ l ≤ 5.
Ključne besede: Komponentna povezanost, komponentna povezavna povezanost, palačinkasti grafi,
toleranca napak.
Math. Subj. Class. (2020): 05C40, 05C75
*Avtorja sta hvaležna neznanim recenzentom za koristne pripombe in predloge.
†Kontaktni avtor.
E-poštna naslova: xhhua@htu.edu.cn (Xiaohui Hua), yllyanglulu@126.com (Lulu Yang)
cb To delo je objavljeno pod licenco https://creativecommons.org/licenses/by/4.0/