Generalized 3-edge-connectivity of Cartesian product graphs

Yuefang Sun

Czechoslovak Mathematical Journal (2015)

  • Volume: 65, Issue: 1, page 107-117
  • ISSN: 0011-4642

Abstract

top
The generalized k -connectivity κ 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 λ k ( G ) = min { λ ( S ) : S ⊆ V ( G ) and | S | = k } , where λ ( S ) denotes the maximum number ℓ of pairwise edge-disjoint trees T 1 , T 2 , ... , T ℓ in G such that S ⊆ V ( T i ) for 1 ≤ i ≤ ℓ . In this paper we prove that for any two connected graphs G and H we have λ 3 ( G □ H ) ≥ λ 3 ( G ) + λ 3 ( H ) , where G □ 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.

How to cite

top

Sun, Yuefang. "Generalized 3-edge-connectivity of Cartesian product graphs." Czechoslovak Mathematical Journal 65.1 (2015): 107-117. <http://eudml.org/doc/270044>.

@article{Sun2015,
abstract = {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 \lbrace \lambda (S)\colon S \subseteq V(G)$ and $|S|= k\rbrace $, 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\le i\le \ell $. In this paper we prove that for any two connected graphs $G$ and $H$ we have $\lambda _3(G\square H)\ge \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.},
author = {Sun, Yuefang},
journal = {Czechoslovak Mathematical Journal},
keywords = {generalized connectivity; generalized edge-connectivity; Cartesian product},
language = {eng},
number = {1},
pages = {107-117},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Generalized 3-edge-connectivity of Cartesian product graphs},
url = {http://eudml.org/doc/270044},
volume = {65},
year = {2015},
}

TY - JOUR
AU - Sun, Yuefang
TI - Generalized 3-edge-connectivity of Cartesian product graphs
JO - Czechoslovak Mathematical Journal
PY - 2015
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 65
IS - 1
SP - 107
EP - 117
AB - 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 \lbrace \lambda (S)\colon S \subseteq V(G)$ and $|S|= k\rbrace $, 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\le i\le \ell $. In this paper we prove that for any two connected graphs $G$ and $H$ we have $\lambda _3(G\square H)\ge \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.
LA - eng
KW - generalized connectivity; generalized edge-connectivity; Cartesian product
UR - http://eudml.org/doc/270044
ER -

References

top
  1. Bondy, J. A., Murty, U. S. R., 10.1007/978-1-84628-970-5_1, Graduate Texts in Mathematics 244 Springer, Berlin (2008). (2008) Zbl1134.05001MR2368647DOI10.1007/978-1-84628-970-5_1
  2. Chartrand, G., Kappor, S. F., Lesniak, L., Lick, D. R., Generalized connectivity in graphs, Bull. Bombay Math. Colloq. 2 (1984), 1-6. (1984) 
  3. Chiue, W.-S., Shieh, B.-S., 10.1016/S0096-3003(98)10041-3, Appl. Math. Comput. 102 (1999), 129-137. (1999) Zbl0927.05048MR1688841DOI10.1016/S0096-3003(98)10041-3
  4. Imrich, W., Klavžar, S., Product Graphs. Structure and Recognition, Wiley-Interscience Series in Discrete Mathematics and Optimization Wiley, New York (2000). (2000) Zbl0963.05002MR1788124
  5. Imrich, W., Klavžar, S., Rall, D. F., Topics in Graph Theory. Graphs and Their Cartesian Product, A K Peters Wellesley (2008). (2008) Zbl1156.05001MR2468851
  6. Klavžar, S., Špacapan, S., 10.1142/S1793557108000102, Asian-Eur. J. Math. 1 (2008), 93-98. (2008) Zbl1144.05312MR2400304DOI10.1142/S1793557108000102
  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. (2012) MR2900353
  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. (2014) Zbl1296.05107MR3211785
  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. (1978) Zbl0368.05037MR0480202
  12. Sabidussi, G., 10.4153/CJM-1957-060-7, Can. J. Math. 9 (1957), 515-525. (1957) Zbl0079.39202MR0094810DOI10.4153/CJM-1957-060-7
  13. Sherwani, N. A., Algorithms for VLSI Physical Design Automation, Kluwer Academic Publishers Boston (1999). (1999) Zbl0926.68059
  14. Špacapan, S., 10.1016/j.aml.2007.06.010, Appl. Math. Lett. 21 (2008), 682-685. (2008) Zbl1152.05340MR2423045DOI10.1016/j.aml.2007.06.010
  15. Xu, J.-M., Yang, C., 10.1016/j.disc.2005.11.010, Discrete Math. 306 (2006), 159-165. (2006) Zbl1085.05042MR2202083DOI10.1016/j.disc.2005.11.010

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.