Geodesic
Generalized connectivity of some total graphs
Czechoslovak Mathematical Journal, Tome 71 (2021) no. 3, pp. 623-640
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

We study the generalized $k$-connectivity $\kappa _k(G)$ as introduced by Hager in 1985, as well as the more recently introduced generalized $k$-edge-connectivity $\lambda _k(G)$. We determine the exact value of $\kappa _k(G)$ and $\lambda _k(G)$ for the line graphs and total graphs of trees, unicyclic graphs, and also for complete graphs for the case $k=3$.
We study the generalized $k$-connectivity $\kappa _k(G)$ as introduced by Hager in 1985, as well as the more recently introduced generalized $k$-edge-connectivity $\lambda _k(G)$. We determine the exact value of $\kappa _k(G)$ and $\lambda _k(G)$ for the line graphs and total graphs of trees, unicyclic graphs, and also for complete graphs for the case $k=3$.
DOI : 10.21136/CMJ.2021.0287-19
Classification : 05C05, 05C40, 05C70, 05C75
Keywords: generalized (edge-)connectivity; line graph; total graph; complete graph 
@article{10_21136_CMJ_2021_0287_19,
     author = {Li, Yinkui and Mao, Yaping and Wang, Zhao and Wei, Zongtian},
     title = {Generalized connectivity of some total graphs},
     journal = {Czechoslovak Mathematical Journal},
     pages = {623--640},
     year = {2021},
     volume = {71},
     number = {3},
     doi = {10.21136/CMJ.2021.0287-19},
     mrnumber = {4295235},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2021.0287-19/}
}
TY  - JOUR
AU  - Li, Yinkui
AU  - Mao, Yaping
AU  - Wang, Zhao
AU  - Wei, Zongtian
TI  - Generalized connectivity of some total graphs
JO  - Czechoslovak Mathematical Journal
PY  - 2021
SP  - 623
EP  - 640
VL  - 71
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2021.0287-19/
DO  - 10.21136/CMJ.2021.0287-19
LA  - en
ID  - 10_21136_CMJ_2021_0287_19
ER  - 
%0 Journal Article
%A Li, Yinkui
%A Mao, Yaping
%A Wang, Zhao
%A Wei, Zongtian
%T Generalized connectivity of some total graphs
%J Czechoslovak Mathematical Journal
%D 2021
%P 623-640
%V 71
%N 3
%U http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2021.0287-19/
%R 10.21136/CMJ.2021.0287-19
%G en
%F 10_21136_CMJ_2021_0287_19
Li, Yinkui; Mao, Yaping; Wang, Zhao; Wei, Zongtian. Generalized connectivity of some total graphs. Czechoslovak Mathematical Journal, Tome 71 (2021) no. 3, pp. 623-640. doi: 10.21136/CMJ.2021.0287-19

[1] Beineke, L. W., (eds.), R. J. Wilson: Topics in Structural Graph Theory. Encyclopedia of Mathematics and its Applications 147. Cambrige University Press, Cambridge (2013). | MR | JFM

[2] Boesch, F. T., Chen, S.: A generalization of line connectivity and optimally invulnerable graphs. SIAM J. Appl. Math. 34 (1978), 657-665. | DOI | MR | JFM

[3] Bondy, J. A., Murty, U. S. R.: Graph Theory. Graduate Texts in Mathematics 244. Springer, Berlin (2008). | DOI | MR | JFM

[4] Chartrand, G., Kappor, S. F., Lesniak, L., Lick, D. R.: Generalized connectivity in graphs. Bull. Bombay Math. Colloq. 2 (1984), 1-6. | MR

[5] Chartrand, G., Okamoto, F., Zhang, P.: Rainbow trees in graphs and generalized connectivity. Networks 55 (2010), 360-367. | DOI | MR | JFM

[6] Chartrand, G., Stewart, M. J.: The connectivity of line-graphs. Math. Ann. 182 (1969), 170-174. | DOI | MR | JFM

[7] Gu, R., Li, X., Shi, Y.: The generalized 3-connectivity of random graphs. Acta Math. Sin., Chin. Ser. 57 (2014), 321-330 Chinese. | JFM

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

[9] Hamada, T., Nonaka, T., Yoshimura, I.: On the connectivity of total graphs. Math. Ann. 196 (1972), 30-38. | DOI | MR | JFM

[10] Kriesell, M.: Edge-disjoint trees containing some given vertices in a graph. J. Comb. Theory, Ser. B 88 (2003), 53-65. | DOI | MR | JFM

[11] Kriesell, M.: Edge disjoint Steiner trees in graphs without large bridges. J. Graph Theory 62 (2009), 188-198. | DOI | MR | JFM

[12] Li, S., Li, X.: Note on the hardness of generalized connectivity. J. Comb. Optim. 24 (2012), 389-396. | DOI | MR | JFM

[13] Li, S., Li, X., Shi, Y.: The minimal size of a graph with generalized connectivity $\kappa_3 = 2$. Australas. J. Comb. 51 (2011), 209-220. | MR | JFM

[14] Li, S., Li, X., Zhou, W.: Sharp bounds for the generalized connectivity $\kappa_3(G)$. Discrete Math. 310 (2010), 2147-2163. | DOI | MR | JFM

[15] Li, S., Li, W., Shi, Y., Sun, H.: On minimally 2-connected graphs with generalized connectivity $\kappa_3=2$. J. Comb. Optim. 34 (2017), 141-164. | DOI | MR | JFM

[16] Li, S., Shi, Y., Tu, J.: The generalized 3-connectivity of Cayley graphs on symmetric groups generated by trees and cycles. Graphs Comb. 33 (2017), 1195-1209. | DOI | MR | JFM

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

[18] Li, X., Mao, Y., Sun, Y.: On the generalized (edge-)connectivity of graphs. Australas. J. Comb. 58 (2014), 304-319. | MR | JFM

[19] Nash-Williams, C. S. J. A.: Edge-disjoint spanning trees of finite graphs. J. Lond. Math. Soc. 36 (1961), 445-450. | DOI | MR | JFM

[20] Okamoto, F., Zhang, P.: The tree connectivity of regular complete bipartite graphs. J. Comb. Math. Comb. Comput. 74 (2010), 279-293. | MR | JFM

[21] Tutte, W. T.: On the problem of decomposing a graph into $n$ connected factors. J. Lond. Math. Soc. 36 (1961), 221-230. | DOI | MR | JFM

Cité par Sources :