Chenxu Yang ; Ping Li ; Yaping Mao ; Eddie Cheng ; Ralf Klasing - Constructing disjoint Steiner trees in Sierpiński graphs

fi:12478 - Fundamenta Informaticae, July 5, 2025, Volume 194, Issue 1 - https://doi.org/10.46298/fi.12478
Constructing disjoint Steiner trees in Sierpiński graphsArticle

Authors: Chenxu Yang ; Ping Li ORCID; Yaping Mao ; Eddie Cheng ; Ralf Klasing

    Let $G$ be a graph and $S\subseteq V(G)$ with $|S|\geq 2$. Then the trees $T_1, T_2, \cdots, T_\ell$ in $G$ are \emph{internally disjoint Steiner trees} connecting $S$ (or $S$-Steiner trees) if $E(T_i) \cap E(T_j )=\emptyset$ and $V(T_i)\cap V(T_j)=S$ for every pair of distinct integers $i,j$, $1 \leq i, j \leq \ell$. Similarly, if we only have the condition $E(T_i) \cap E(T_j )=\emptyset$ but without the condition $V(T_i)\cap V(T_j)=S$, then they are \emph{edge-disjoint Steiner trees}. The \emph{generalized $k$-connectivity}, denoted by $κ_k(G)$, of a graph $G$, is defined as $κ_k(G)=\min\{κ_G(S)|S \subseteq V(G) \ \textrm{and} \ |S|=k \}$, where $κ_G(S)$ is the maximum number of internally disjoint $S$-Steiner trees. The \emph{generalized local edge-connectivity} $λ_{G}(S)$ is the maximum number of edge-disjoint Steiner trees connecting $S$ in $G$. The {\it generalized $k$-edge-connectivity} $λ_k(G)$ of $G$ is defined as $λ_k(G)=\min\{λ_{G}(S)\,|\,S\subseteq V(G) \ and \ |S|=k\}$. These measures are generalizations of the concepts of connectivity and edge-connectivity, and they and can be used as measures of vulnerability of networks. It is, in general, difficult to compute these generalized connectivities. However, there are precise results for some special classes of graphs. In this paper, we obtain the exact value of $λ_{k}(S(n,\ell))$ for $3\leq k\leq \ell^n$, and the exact value of $κ_{k}(S(n,\ell))$ for $3\leq k\leq \ell$, where $S(n, \ell)$ is the Sierpiński graphs with order $\ell^n$. As a direct consequence, these graphs provide additional interesting examples when $λ_{k}(S(n,\ell))=κ_{k}(S(n,\ell))$. We also study the some network properties of Sierpiński graphs.


    Volume: Volume 194, Issue 1
    Published on: July 5, 2025
    Accepted on: January 15, 2025
    Submitted on: October 27, 2023
    Keywords: Combinatorics,Data Structures and Algorithms