Volume 194, Issue 1


1. Equational theory of ordinals with addition and left multiplication by $ω$

Christian Choffrut.
We show that the equational theory of the structure $\langle ω^ω: (x,y)\mapsto x+y, x\mapsto ωx \rangle $ is finitely axiomatizable and give a simple axiom schema when the domain is the set of transfinite ordinals. We give an algorithm that given a pair of terms $(E,F)$ decides in linear time with respect of their common length whether or not $E=F$ is a consequence of the axioms.

2. Constructing disjoint Steiner trees in Sierpiński graphs

Chenxu Yang ; Ping Li ; 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 […]