Article
| Title: | A lower bound for the 3-pendant tree-connectivity of lexicographic product graphs (English) |
| Author: | Mao, Yaping |
| Author: | Melekian, Christopher |
| Author: | Cheng, Eddie |
| Language: | English |
| Journal: | Czechoslovak Mathematical Journal |
| ISSN: | 0011-4642 (print) |
| ISSN: | 1572-9141 (online) |
| Volume: | 73 |
| Issue: | 1 |
| Year: | 2023 |
| Pages: | 237-244 |
| Summary lang: | English |
| . | |
| Category: | math |
| . | |
| 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. (English) |
| Keyword: | connectivity |
| Keyword: | Steiner tree |
| Keyword: | internally disjoint Steiner tree |
| Keyword: | packing |
| Keyword: | pendant tree-connectivity, lexicographic product |
| MSC: | 05C05 |
| MSC: | 05C40 |
| MSC: | 05C70 |
| MSC: | 05C76 |
| idZBL: | Zbl 07655765 |
| idMR: | MR4541099 |
| DOI: | 10.21136/CMJ.2022.0057-22 |
| . | |
| Date available: | 2023-02-03T11:13:45Z |
| Last updated: | 2023-09-13 |
| Stable URL: | http://hdl.handle.net/10338.dmlcz/151514 |
| . | |
| Reference: | [1] Hager, M.: Pendant tree-connectivity.J. Comb. Theory, Ser. B 38 (1985), 179-189. Zbl 0566.05041, MR 0787327, 10.1016/0095-8956(85)90083-8 |
| Reference: | [2] Hind, H. R., Oellermann, O.: Menger-type results for three or more vertices.Congr. Numerantium 113 (1996), 179-204. Zbl 0974.05047, MR 1393709 |
| Reference: | [3] Li, X., Mao, Y.: The generalized 3-connectivity of lexicographic product graphs.Discrete Math. Theor. Comput. Sci. 16 (2014), 339-354. Zbl 1294.05105, MR 3223294 |
| Reference: | [4] Li, X., Mao, Y.: Generalized Connectivity of Graphs.SpringerBriefs in Mathematics. Springer, Cham (2016). Zbl 1346.05001, MR 3496995, 10.1007/978-3-319-33828-6 |
| Reference: | [5] West, D. B.: Introduction to Graph Theory.Prentice Hall, Upper Saddle River (1996). Zbl 0845.05001, MR 1367739 |
| Reference: | [6] Yang, C., Xu, J.-M.: Connectivity of lexicographic product and direct product of graphs.Ars Comb. 111 (2013), 3-12. Zbl 1313.05212, MR 3100156 |
| . |
Fulltext not available (moving wall 24 months)
Search
Partner of
