Geodesic
A lower bound for the 3-pendant tree-connectivity of lexicographic product graphs
Czechoslovak Mathematical Journal, Tome 73 (2023) no. 1, pp. 237-244
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
DOI : 10.21136/CMJ.2022.0057-22
Classification : 05C05, 05C40, 05C70, 05C76
Keywords: connectivity; Steiner tree; internally disjoint Steiner tree; packing; pendant tree-connectivity, lexicographic product 
@article{10_21136_CMJ_2022_0057_22,
     author = {Mao, Yaping and Melekian, Christopher and Cheng, Eddie},
     title = {A lower bound for the 3-pendant tree-connectivity of lexicographic product graphs},
     journal = {Czechoslovak Mathematical Journal},
     pages = {237--244},
     year = {2023},
     volume = {73},
     number = {1},
     doi = {10.21136/CMJ.2022.0057-22},
     mrnumber = {4541099},
     zbl = {07655765},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2022.0057-22/}
}
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
SP  - 237
EP  - 244
VL  - 73
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2022.0057-22/
DO  - 10.21136/CMJ.2022.0057-22
LA  - en
ID  - 10_21136_CMJ_2022_0057_22
ER  - 
%0 Journal Article
%A Mao, Yaping
%A Melekian, Christopher
%A Cheng, Eddie
%T A lower bound for the 3-pendant tree-connectivity of lexicographic product graphs
%J Czechoslovak Mathematical Journal
%D 2023
%P 237-244
%V 73
%N 1
%U http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2022.0057-22/
%R 10.21136/CMJ.2022.0057-22
%G en
%F 10_21136_CMJ_2022_0057_22
Mao, Yaping; Melekian, Christopher; Cheng, Eddie. A lower bound for the 3-pendant tree-connectivity of lexicographic product graphs. Czechoslovak Mathematical Journal, Tome 73 (2023) no. 1, pp. 237-244. doi: 10.21136/CMJ.2022.0057-22

[1] Hager, M.: Pendant tree-connectivity. J. Comb. Theory, Ser. B 38 (1985), 179-189. | DOI | MR | JFM

[2] Hind, H. R., Oellermann, O.: Menger-type results for three or more vertices. Congr. Numerantium 113 (1996), 179-204. | MR | JFM

[3] Li, X., Mao, Y.: The generalized 3-connectivity of lexicographic product graphs. Discrete Math. Theor. Comput. Sci. 16 (2014), 339-354. | MR | JFM

[4] Li, X., Mao, Y.: Generalized Connectivity of Graphs. SpringerBriefs in Mathematics. Springer, Cham (2016). | DOI | MR | JFM

[5] West, D. B.: Introduction to Graph Theory. Prentice Hall, Upper Saddle River (1996). | MR | JFM

[6] Yang, C., Xu, J.-M.: Connectivity of lexicographic product and direct product of graphs. Ars Comb. 111 (2013), 3-12. | MR | JFM

Cité par Sources :