A lower bound for the 3-pendant tree-connectivity of lexicographic product graphs

Mao, Yaping, Melekian, Christopher, and Cheng, Eddie. "A lower bound for the 3-pendant tree-connectivity of lexicographic product graphs." Czechoslovak Mathematical Journal 73.1 (2023): 237-244. <http://eudml.org/doc/299568>.

@article{Mao2023,
abstract = {For a connected graph $G=(V,E)$ and a set $S \subseteq V(G)$ with at least two vertices, an $S$-Steiner tree is a subgraph $T = (V^\{\prime \},E^\{\prime \})$ of $G$ that is a tree with $S \subseteq V^\{\prime \}$. If the degree of each vertex of $S$ in $T$ is equal to 1, then $T$ is called a pendant $S$-Steiner tree. Two $S$-Steiner trees are internally disjoint if they share no vertices other than $S$ and have no edges in common. For $S\subseteq V(G)$ and $|S|\ge 2$, the pendant tree-connectivity $\tau _G(S)$ is the maximum number of internally disjoint pendant $S$-Steiner trees in $G$, and for $k \ge 2$, the $k$-pendant tree-connectivity $\tau _k(G)$ is the minimum value of $\tau _G(S)$ over all sets $S$ of $k$ vertices. We derive a lower bound for $\tau _3(G\circ H)$, where $G$ and $H$ are connected graphs and $\circ $ denotes the lexicographic product.},
author = {Mao, Yaping, Melekian, Christopher, Cheng, Eddie},
journal = {Czechoslovak Mathematical Journal},
keywords = {connectivity; Steiner tree; internally disjoint Steiner tree; packing; pendant tree-connectivity; lexicographic product},
language = {eng},
number = {1},
pages = {237-244},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {A lower bound for the 3-pendant tree-connectivity of lexicographic product graphs},
url = {http://eudml.org/doc/299568},
volume = {73},
year = {2023},
}

TY - JOUR
AU - Mao, Yaping
AU - Melekian, Christopher
AU - Cheng, Eddie
TI - A lower bound for the 3-pendant tree-connectivity of lexicographic product graphs
JO - Czechoslovak Mathematical Journal
PY - 2023
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 73
IS - 1
SP - 237
EP - 244
AB - For a connected graph $G=(V,E)$ and a set $S \subseteq V(G)$ with at least two vertices, an $S$-Steiner tree is a subgraph $T = (V^{\prime },E^{\prime })$ of $G$ that is a tree with $S \subseteq V^{\prime }$. If the degree of each vertex of $S$ in $T$ is equal to 1, then $T$ is called a pendant $S$-Steiner tree. Two $S$-Steiner trees are internally disjoint if they share no vertices other than $S$ and have no edges in common. For $S\subseteq V(G)$ and $|S|\ge 2$, the pendant tree-connectivity $\tau _G(S)$ is the maximum number of internally disjoint pendant $S$-Steiner trees in $G$, and for $k \ge 2$, the $k$-pendant tree-connectivity $\tau _k(G)$ is the minimum value of $\tau _G(S)$ over all sets $S$ of $k$ vertices. We derive a lower bound for $\tau _3(G\circ H)$, where $G$ and $H$ are connected graphs and $\circ $ denotes the lexicographic product.
LA - eng
KW - connectivity; Steiner tree; internally disjoint Steiner tree; packing; pendant tree-connectivity; lexicographic product
UR - http://eudml.org/doc/299568
ER -