| Title:
|
Generalized connectivity of some total graphs (English) |
| Author:
|
Li, Yinkui |
| Author:
|
Mao, Yaping |
| Author:
|
Wang, Zhao |
| Author:
|
Wei, Zongtian |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
71 |
| Issue:
|
3 |
| Year:
|
2021 |
| Pages:
|
623-640 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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$. (English) |
| Keyword:
|
generalized (edge-)connectivity |
| Keyword:
|
line graph |
| Keyword:
|
total graph |
| Keyword:
|
complete graph |
| MSC:
|
05C05 |
| MSC:
|
05C40 |
| MSC:
|
05C70 |
| MSC:
|
05C75 |
| idZBL:
|
07396187 |
| idMR:
|
MR4295235 |
| DOI:
|
10.21136/CMJ.2021.0287-19 |
| . |
| Date available:
|
2021-08-02T08:00:58Z |
| Last updated:
|
2023-10-02 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/149045 |
| . |
| Reference:
|
[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). Zbl 1266.05002, MR 3059595 |
| Reference:
|
[2] Boesch, F. T., Chen, S.: A generalization of line connectivity and optimally invulnerable graphs.SIAM J. Appl. Math. 34 (1978), 657-665. Zbl 0386.05042, MR 0505837, 10.1137/0134052 |
| Reference:
|
[3] Bondy, J. A., Murty, U. S. R.: Graph Theory.Graduate Texts in Mathematics 244. Springer, Berlin (2008). Zbl 1134.05001, MR 2368647, 10.1007/978-1-84628-970-5 |
| Reference:
|
[4] Chartrand, G., Kappor, S. F., Lesniak, L., Lick, D. R.: Generalized connectivity in graphs.Bull. Bombay Math. Colloq. 2 (1984), 1-6. MR 2107429 |
| Reference:
|
[5] Chartrand, G., Okamoto, F., Zhang, P.: Rainbow trees in graphs and generalized connectivity.Networks 55 (2010), 360-367. Zbl 1205.05085, MR 2666306, 10.1002/net.20339 |
| Reference:
|
[6] Chartrand, G., Stewart, M. J.: The connectivity of line-graphs.Math. Ann. 182 (1969), 170-174. Zbl 0167.52203, MR 0277428, 10.1007/BF01350320 |
| Reference:
|
[7] Gu, R., Li, X., Shi, Y.: The generalized 3-connectivity of random graphs.Acta Math. Sin., Chin. Ser. 57 (2014), 321-330 Chinese. Zbl 1313.05205 |
| Reference:
|
[8] 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:
|
[9] Hamada, T., Nonaka, T., Yoshimura, I.: On the connectivity of total graphs.Math. Ann. 196 (1972), 30-38. Zbl 0215.33802, MR 0295959, 10.1007/BF01419429 |
| Reference:
|
[10] Kriesell, M.: Edge-disjoint trees containing some given vertices in a graph.J. Comb. Theory, Ser. B 88 (2003), 53-65. Zbl 1027.05023, MR 1973259, 10.1016/S0095-8956(02)00013-8 |
| Reference:
|
[11] Kriesell, M.: Edge disjoint Steiner trees in graphs without large bridges.J. Graph Theory 62 (2009), 188-198. Zbl 1183.05018, MR 2555097, 10.1002/jgt.20389 |
| Reference:
|
[12] Li, S., Li, X.: Note on the hardness of generalized connectivity.J. Comb. Optim. 24 (2012), 389-396. Zbl 1261.90078, MR 2970506, 10.1007/s10878-011-9399-x |
| Reference:
|
[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. Zbl 1233.05120, MR 2866960 |
| Reference:
|
[14] Li, S., Li, X., Zhou, W.: Sharp bounds for the generalized connectivity $\kappa_3(G)$.Discrete Math. 310 (2010), 2147-2163. Zbl 1258.05057, MR 2651812, 10.1016/j.disc.2010.04.011 |
| Reference:
|
[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. Zbl 1410.05107, MR 3661071, 10.1007/s10878-016-0075-z |
| Reference:
|
[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. Zbl 1383.05158, MR 3714525, 10.1007/s00373-017-1837-9 |
| Reference:
|
[17] 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:
|
[18] Li, X., Mao, Y., Sun, Y.: On the generalized (edge-)connectivity of graphs.Australas. J. Comb. 58 (2014), 304-319. Zbl 1296.05107, MR 3211785 |
| Reference:
|
[19] Nash-Williams, C. S. J. A.: Edge-disjoint spanning trees of finite graphs.J. Lond. Math. Soc. 36 (1961), 445-450. Zbl 0102.38805, MR 0133253, 10.1112/jlms/s1-36.1.445 |
| Reference:
|
[20] Okamoto, F., Zhang, P.: The tree connectivity of regular complete bipartite graphs.J. Comb. Math. Comb. Comput. 74 (2010), 279-293. Zbl 1223.05159, MR 2675906 |
| Reference:
|
[21] Tutte, W. T.: On the problem of decomposing a graph into $n$ connected factors.J. Lond. Math. Soc. 36 (1961), 221-230. Zbl 0096.38001, MR 0140438, 10.1112/jlms/s1-36.1.221 |
| . |
