Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
generalized connectivity; generalized edge-connectivity; Cartesian product
generalized connectivity; generalized edge-connectivity; Cartesian product
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.
References:
[1] 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_1 | MR 2368647 | Zbl 1134.05001
[2] Chartrand, G., Kappor, S. F., Lesniak, L., Lick, D. R.: Generalized connectivity in graphs. Bull. Bombay Math. Colloq. 2 (1984), 1-6.
[3] Chiue, W.-S., Shieh, B.-S.: On connectivity of the Cartesian product of two graphs. Appl. Math. Comput. 102 (1999), 129-137. DOI 10.1016/S0096-3003(98)10041-3 | MR 1688841 | Zbl 0927.05048
[4] Imrich, W., Klavžar, S.: Product Graphs. Structure and Recognition. Wiley-Interscience Series in Discrete Mathematics and Optimization Wiley, New York (2000). MR 1788124 | Zbl 0963.05002
[5] Imrich, W., Klavžar, S., Rall, D. F.: Topics in Graph Theory. Graphs and Their Cartesian Product. A K Peters Wellesley (2008). MR 2468851 | Zbl 1156.05001
[6] Klavžar, S., Špacapan, S.: On the edge-connectivity of Cartesian product graphs. Asian-Eur. J. Math. 1 (2008), 93-98. DOI 10.1142/S1793557108000102 | MR 2400304 | Zbl 1144.05312
[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
[8] Li, X., Mao, Y.: A survey on the generalized connectivity of graphs. ArXiv:1207.1838v2 [math.CO].
[9] Li, X., Mao, Y., Sun, Y.: On the generalized (edge-)connectivity of graphs. Australas. J. Comb. (electronic only) 58 (2014), 304-319. MR 3211785 | Zbl 1296.05107
[10] Li, X., Mao, Y., Wang, L.: Graphs with large generalized 3-edge-connectivity. ArXiv:1201. 3699v1 [math.CO].
[11] Liouville, B.: Sur la connectivité des produits de graphes. C. R. Acad. Sci., Paris, Sér. A 286 (1978), 363-365 French. MR 0480202 | Zbl 0368.05037
[12] Sabidussi, G.: Graphs with given group and given graph-theoretical properties. Can. J. Math. 9 (1957), 515-525. DOI 10.4153/CJM-1957-060-7 | MR 0094810 | Zbl 0079.39202
[13] Sherwani, N. A.: Algorithms for VLSI Physical Design Automation. Kluwer Academic Publishers Boston (1999). Zbl 0926.68059
[14] Špacapan, S.: Connectivity of Cartesian products of graphs. Appl. Math. Lett. 21 (2008), 682-685. DOI 10.1016/j.aml.2007.06.010 | MR 2423045 | Zbl 1152.05340
[15] Xu, J.-M., Yang, C.: Connectivity of Cartesian product graphs. Discrete Math. 306 (2006), 159-165. DOI 10.1016/j.disc.2005.11.010 | MR 2202083 | Zbl 1085.05042
Search
Partner of
