Article
Full entry | Fulltext not available
(moving wall
24 months)
Feedback
Keywords:
connectivity; Steiner tree; internally disjoint Steiner tree; packing; pendant tree-connectivity, lexicographic product
connectivity; Steiner tree; internally disjoint Steiner tree; packing; pendant tree-connectivity, lexicographic product
Summary:
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',E')$ of $G$ that is a tree with $S \subseteq V'$. 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 {\it internally disjoint} if they share no vertices other than $S$ and have no edges in common. For $S\subseteq V(G)$ and $|S|\geq 2$, the pendant tree-connectivity $\tau _G(S)$ is the maximum number of internally disjoint pendant $S$-Steiner trees in $G$, and for $k \geq 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.
References:
[1] Hager, M.: Pendant tree-connectivity. J. Comb. Theory, Ser. B 38 (1985), 179-189. DOI 10.1016/0095-8956(85)90083-8 | MR 0787327 | Zbl 0566.05041
[2] Hind, H. R., Oellermann, O.: Menger-type results for three or more vertices. Congr. Numerantium 113 (1996), 179-204. MR 1393709 | Zbl 0974.05047
[3] Li, X., Mao, Y.: The generalized 3-connectivity of lexicographic product graphs. Discrete Math. Theor. Comput. Sci. 16 (2014), 339-354. MR 3223294 | Zbl 1294.05105
[4] Li, X., Mao, Y.: Generalized Connectivity of Graphs. SpringerBriefs in Mathematics. Springer, Cham (2016). DOI 10.1007/978-3-319-33828-6 | MR 3496995 | Zbl 1346.05001
[5] West, D. B.: Introduction to Graph Theory. Prentice Hall, Upper Saddle River (1996). MR 1367739 | Zbl 0845.05001
[6] Yang, C., Xu, J.-M.: Connectivity of lexicographic product and direct product of graphs. Ars Comb. 111 (2013), 3-12. MR 3100156 | Zbl 1313.05212
Search
Partner of
