Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
generalized (edge-)connectivity; line graph; total graph; complete graph
generalized (edge-)connectivity; line graph; total graph; complete graph
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$.
References:
[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 3059595 | Zbl 1266.05002
[2] Boesch, F. T., Chen, S.: A generalization of line connectivity and optimally invulnerable graphs. SIAM J. Appl. Math. 34 (1978), 657-665. DOI 10.1137/0134052 | MR 0505837 | Zbl 0386.05042
[3] Bondy, J. A., Murty, U. S. R.: Graph Theory. Graduate Texts in Mathematics 244. Springer, Berlin (2008). DOI 10.1007/978-1-84628-970-5 | MR 2368647 | Zbl 1134.05001
[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
[5] Chartrand, G., Okamoto, F., Zhang, P.: Rainbow trees in graphs and generalized connectivity. Networks 55 (2010), 360-367. DOI 10.1002/net.20339 | MR 2666306 | Zbl 1205.05085
[6] Chartrand, G., Stewart, M. J.: The connectivity of line-graphs. Math. Ann. 182 (1969), 170-174. DOI 10.1007/BF01350320 | MR 0277428 | Zbl 0167.52203
[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
[8] Hager, M.: Pendant tree-connectivity. J. Comb. Theory, Ser. B 38 (1985), 179-189. DOI 10.1016/0095-8956(85)90083-8 | MR 0787327 | Zbl 0566.05041
[9] Hamada, T., Nonaka, T., Yoshimura, I.: On the connectivity of total graphs. Math. Ann. 196 (1972), 30-38. DOI 10.1007/BF01419429 | MR 0295959 | Zbl 0215.33802
[10] Kriesell, M.: Edge-disjoint trees containing some given vertices in a graph. J. Comb. Theory, Ser. B 88 (2003), 53-65. DOI 10.1016/S0095-8956(02)00013-8 | MR 1973259 | Zbl 1027.05023
[11] Kriesell, M.: Edge disjoint Steiner trees in graphs without large bridges. J. Graph Theory 62 (2009), 188-198. DOI 10.1002/jgt.20389 | MR 2555097 | Zbl 1183.05018
[12] Li, S., Li, X.: Note on the hardness of generalized connectivity. J. Comb. Optim. 24 (2012), 389-396. DOI 10.1007/s10878-011-9399-x | MR 2970506 | Zbl 1261.90078
[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 2866960 | Zbl 1233.05120
[14] Li, S., Li, X., Zhou, W.: Sharp bounds for the generalized connectivity $\kappa_3(G)$. Discrete Math. 310 (2010), 2147-2163. DOI 10.1016/j.disc.2010.04.011 | MR 2651812 | Zbl 1258.05057
[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 10.1007/s10878-016-0075-z | MR 3661071 | Zbl 1410.05107
[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 10.1007/s00373-017-1837-9 | MR 3714525 | Zbl 1383.05158
[17] Li, X., Mao, Y.: Generalized Connectivity of Graphs. SpringerBriefs in Mathematics. Springer, Cham (2016). DOI 10.1007/978-3-319-33828-6 | MR 3496995 | Zbl 1346.05001
[18] Li, X., Mao, Y., Sun, Y.: On the generalized (edge-)connectivity of graphs. Australas. J. Comb. 58 (2014), 304-319. MR 3211785 | Zbl 1296.05107
[19] Nash-Williams, C. S. J. A.: Edge-disjoint spanning trees of finite graphs. J. Lond. Math. Soc. 36 (1961), 445-450. DOI 10.1112/jlms/s1-36.1.445 | MR 0133253 | Zbl 0102.38805
[20] Okamoto, F., Zhang, P.: The tree connectivity of regular complete bipartite graphs. J. Comb. Math. Comb. Comput. 74 (2010), 279-293. MR 2675906 | Zbl 1223.05159
[21] Tutte, W. T.: On the problem of decomposing a graph into $n$ connected factors. J. Lond. Math. Soc. 36 (1961), 221-230. DOI 10.1112/jlms/s1-36.1.221 | MR 0140438 | Zbl 0096.38001
Search
Partner of
