| 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:
|
2025-04-07 |
| 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 |
| . |
