Geodesic
Generalized 3-edge-connectivity of Cartesian product graphs
Czechoslovak Mathematical Journal, Tome 65 (2015) no. 1, pp. 107-117
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
DOI : 10.1007/s10587-015-0162-9
Classification : 05C40, 05C76
Keywords: generalized connectivity; generalized edge-connectivity; Cartesian product 
@article{10_1007_s10587_015_0162_9,
     author = {Sun, Yuefang},
     title = {Generalized 3-edge-connectivity of {Cartesian} product graphs},
     journal = {Czechoslovak Mathematical Journal},
     pages = {107--117},
     year = {2015},
     volume = {65},
     number = {1},
     doi = {10.1007/s10587-015-0162-9},
     mrnumber = {3336027},
     zbl = {06433723},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1007/s10587-015-0162-9/}
}
TY  - JOUR
AU  - Sun, Yuefang
TI  - Generalized 3-edge-connectivity of Cartesian product graphs
JO  - Czechoslovak Mathematical Journal
PY  - 2015
SP  - 107
EP  - 117
VL  - 65
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.1007/s10587-015-0162-9/
DO  - 10.1007/s10587-015-0162-9
LA  - en
ID  - 10_1007_s10587_015_0162_9
ER  - 
%0 Journal Article
%A Sun, Yuefang
%T Generalized 3-edge-connectivity of Cartesian product graphs
%J Czechoslovak Mathematical Journal
%D 2015
%P 107-117
%V 65
%N 1
%U http://geodesic.mathdoc.fr/articles/10.1007/s10587-015-0162-9/
%R 10.1007/s10587-015-0162-9
%G en
%F 10_1007_s10587_015_0162_9
Sun, Yuefang. Generalized 3-edge-connectivity of Cartesian product graphs. Czechoslovak Mathematical Journal, Tome 65 (2015) no. 1, pp. 107-117. doi: 10.1007/s10587-015-0162-9

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

[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 | MR | Zbl

[4] Imrich, W., Klavžar, S.: Product Graphs. Structure and Recognition. Wiley-Interscience Series in Discrete Mathematics and Optimization Wiley, New York (2000). | MR | Zbl

[5] Imrich, W., Klavžar, S., Rall, D. F.: Topics in Graph Theory. Graphs and Their Cartesian Product. A K Peters Wellesley (2008). | MR | Zbl

[6] Klavžar, S., Špacapan, S.: On the edge-connectivity of Cartesian product graphs. Asian-Eur. J. Math. 1 (2008), 93-98. | DOI | MR | Zbl

[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

[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 | Zbl

[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 | Zbl

[12] Sabidussi, G.: Graphs with given group and given graph-theoretical properties. Can. J. Math. 9 (1957), 515-525. | DOI | MR | Zbl

[13] Sherwani, N. A.: Algorithms for VLSI Physical Design Automation. Kluwer Academic Publishers Boston (1999). | Zbl

[14] Špacapan, S.: Connectivity of Cartesian products of graphs. Appl. Math. Lett. 21 (2008), 682-685. | DOI | MR | Zbl

[15] Xu, J.-M., Yang, C.: Connectivity of Cartesian product graphs. Discrete Math. 306 (2006), 159-165. | DOI | MR | Zbl

Cité par Sources :