| Title:
|
Generalized 3-edge-connectivity of Cartesian product graphs (English) |
| Author:
|
Sun, Yuefang |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
65 |
| Issue:
|
1 |
| Year:
|
2015 |
| Pages:
|
107-117 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
The generalized $k$-connectivity $\kappa _{k}(G)$ of a graph $G$ was introduced by Chartrand et al. in 1984. As a natural counterpart of this concept, Li et al. in 2011 introduced the concept of generalized $k$-edge-connectivity which is defined as $\lambda _k(G) = \min \{\lambda (S)\colon S \subseteq V(G)$ and $|S|= k\}$, where $\lambda (S)$ denotes the maximum number $\ell $ of pairwise edge-disjoint trees $T_1, T_2, \ldots , T_{\ell }$ in $G$ such that $S\subseteq V(T_i)$ for $1\leq i\leq \ell $. In this paper we prove that for any two connected graphs $G$ and $H$ we have $\lambda _3(G\square H)\geq \lambda _3(G)+\lambda _3(H)$, where $G\square H$ is the Cartesian product of $G$ and $H$. Moreover, the bound is sharp. We also obtain the precise values for the generalized 3-edge-connectivity of the Cartesian product of some special graph classes. (English) |
| Keyword:
|
generalized connectivity |
| Keyword:
|
generalized edge-connectivity |
| Keyword:
|
Cartesian product |
| MSC:
|
05C40 |
| MSC:
|
05C76 |
| idZBL:
|
Zbl 06433723 |
| idMR:
|
MR3336027 |
| DOI:
|
10.1007/s10587-015-0162-9 |
| . |
| Date available:
|
2015-04-01T12:24:03Z |
| Last updated:
|
2020-07-03 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/144215 |
| . |
| Reference:
|
[1] 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_1 |
| Reference:
|
[2] Chartrand, G., Kappor, S. F., Lesniak, L., Lick, D. R.: Generalized connectivity in graphs.Bull. Bombay Math. Colloq. 2 (1984), 1-6. |
| Reference:
|
[3] Chiue, W.-S., Shieh, B.-S.: On connectivity of the Cartesian product of two graphs.Appl. Math. Comput. 102 (1999), 129-137. Zbl 0927.05048, MR 1688841, 10.1016/S0096-3003(98)10041-3 |
| Reference:
|
[4] Imrich, W., Klavžar, S.: Product Graphs. Structure and Recognition.Wiley-Interscience Series in Discrete Mathematics and Optimization Wiley, New York (2000). Zbl 0963.05002, MR 1788124 |
| Reference:
|
[5] Imrich, W., Klavžar, S., Rall, D. F.: Topics in Graph Theory. Graphs and Their Cartesian Product.A K Peters Wellesley (2008). Zbl 1156.05001, MR 2468851 |
| Reference:
|
[6] Klavžar, S., Špacapan, S.: On the edge-connectivity of Cartesian product graphs.Asian-Eur. J. Math. 1 (2008), 93-98. Zbl 1144.05312, MR 2400304, 10.1142/S1793557108000102 |
| Reference:
|
[7] Li, H., Li, X., Sun, Y.: The generalized 3-connectivity of Cartesian product graphs.Discrete Math. Theor. Comput. Sci. (electronic only) 14 (2012), 43-54. MR 2900353 |
| Reference:
|
[8] Li, X., Mao, Y.: A survey on the generalized connectivity of graphs.ArXiv:1207.1838v2 [math.CO]. |
| Reference:
|
[9] Li, X., Mao, Y., Sun, Y.: On the generalized (edge-)connectivity of graphs.Australas. J. Comb. (electronic only) 58 (2014), 304-319. Zbl 1296.05107, MR 3211785 |
| Reference:
|
[10] Li, X., Mao, Y., Wang, L.: Graphs with large generalized 3-edge-connectivity.ArXiv:1201. 3699v1 [math.CO]. |
| Reference:
|
[11] Liouville, B.: Sur la connectivité des produits de graphes.C. R. Acad. Sci., Paris, Sér. A 286 (1978), 363-365 French. Zbl 0368.05037, MR 0480202 |
| Reference:
|
[12] Sabidussi, G.: Graphs with given group and given graph-theoretical properties.Can. J. Math. 9 (1957), 515-525. Zbl 0079.39202, MR 0094810, 10.4153/CJM-1957-060-7 |
| Reference:
|
[13] Sherwani, N. A.: Algorithms for VLSI Physical Design Automation.Kluwer Academic Publishers Boston (1999). Zbl 0926.68059 |
| Reference:
|
[14] Špacapan, S.: Connectivity of Cartesian products of graphs.Appl. Math. Lett. 21 (2008), 682-685. Zbl 1152.05340, MR 2423045, 10.1016/j.aml.2007.06.010 |
| Reference:
|
[15] Xu, J.-M., Yang, C.: Connectivity of Cartesian product graphs.Discrete Math. 306 (2006), 159-165. Zbl 1085.05042, MR 2202083, 10.1016/j.disc.2005.11.010 |
| . |
