Abstract
The generalized \(k\)-edge-connectivity \(\lambda _k(G)\) of a graph \(G\) is a natural generalization of the concept of edge-connectivity. The generalized edge-connectivity has many applications in networks. The lexicographic product of two graphs \(G\) and \(H\), denoted by \(G\circ H\), is an important method to construct large graphs from small ones. In this paper, we mainly study the generalized 3-edge-connectivity of \(G \circ H\), and get lower and upper bounds of \(\lambda _3(G \circ H)\). An example is given to show that all bounds are sharp.
Supported by NSFC No. 11371205 and PCSIRT.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Barden, B., Libeskind-Hadas, R., Davis, J., Williams, W.: On edge-disjoint spanning trees in hypercubes. Infor. Proces. Lett. 70, 13–16 (1999)
Beineke, L.W., Wilson, R.J.: Topics in Structural Graph Theory. Cambrige University Press, Cambrige (2013)
Bondy, J.A., Murty, U.S.R.: Graph Theory. GTM 244. Springer, Berlin (2008)
Brešar, B., Špacapan, S.: Edge connectivity of strong products of graphs. Discuss. Math. Graph Theory 27, 333–343 (2007)
Chartrand, G., Okamoto, F., Zhang, P.: Rainbow trees in graphs and generalized connectivity. Networks 55(4), 360–367 (2010)
Cheng, X., Du, D.: Steiner Trees in Industry. Kluwer Academic Publisher, Dordrecht (2001)
Du, D., Hu, X.: Steiner Tree Problems in Computer Communication Networks. World Scientific, River Edge (2008)
Feng, M., Xu, M., Wang, K.: Identifying codes of lexicographic product of graphs. Electron. J. Comb. 19(4), 56–63 (2012)
Grötschel, M.: The Steiner tree packing problem in \(VLSI\) design. Math. Program. 78, 265–281 (1997)
Hammack, R., Imrich, W., Klavz̆ar, S.: Handbook of Product Graphs, 2nd edn. CRC Press, Boca Raton (2011)
Hager, M.: Pendant tree-connectivity. J. Combin. Theory 38, 179–189 (1985)
Imrich, W., Klavžar, S.: Product Graphs: Structure and Recognition. Wiley, New York (2000)
Klavžar, S., Špacapan, S.: On the edge-connectivity of Cartesian product graphs. Asian-Europ. J. Math. 1, 93–98 (2008)
Ku, S., Wang, B., Hung, T.: Constructing edge-disjoint spanning trees in product networks. IEEE Trans. Parallel Distrib. Syst. 14(3), 213–221 (2003)
Li, F., Xu, Z., Zhao, H., Wang, W.: On the number of spanning trees of the lexicographic product of networks. Sci. China Ser. F 42, 949–959 (2012)
Li, H., Li, X., Sun, Y.: The generalied 3-connectivity of Cartesian product graphs. Discrete Math. Theor. Comput. Sci. 14(1), 43–54 (2012)
Li, H., Li, X., Mao, Y.: On extremal graphs with at most two internally disjoint Steiner trees connecting any three vertices. Bull. Malays. Math. Sci. Soc. 37(2,3), 747–756 (2014)
Li, S., Li, X., Zhou, W.: Sharp bounds for the generalized connectivity \(\kappa _3(G)\). Discrete Math. 310, 2147–2163 (2010)
Li, S., Li, W., Li, X.: The generalized connectivity of complete equipartition \(3\)-partite graphs. Bull. Malays. Math. Sci. Soc. 37(1,2), 103–121 (2014)
Li, X., Mao, Y.: The generalized 3-connectivity of lexicographic product graphs. Discrete Math. Theor. Comput. Sci. 16(1), 339–354 (2014)
Li, X., Mao, Y.: The minimal size of a graph with given generalized 3-edge-connectivity. Accepted for publication in Ars Comb
Li, X., Mao, Y., Sun, Y.: On the generalized (edge-)connectivity of graphs. Austral. J. Comb. 58, 304–319 (2014)
Nash Williams, CStJA: Edge-disjonint spanning trees of finite graphs. J. London Math. Soc. 36, 445–450 (1961)
Oellermann, O.R.: Connectivity and edge-connectivity in graphs: a survey. Cong. Numer. 116, 231–252 (1996)
Ozeki, K., Yamashita, T.: Spanning trees: a survey. Graphs Combin. 27(1), 1–26 (2011)
Palmer, E.: On the spanning tree packing number of a graph: a survey. Discrete Math. 230, 13–21 (2001)
Sherwani, N.: Algorithms for \(VLSI\) Physical Design Automation, 3rd edn. Kluwer Academic Publishers, London (1999)
Sun, Y.: Generalized 3-edge-connectivity of Cartesian product graphs. Accepted for publication in Czech. Math. J.
Tutte, W.: On the problem of decomposing a graph into \(n\) connected factors. J. London Math. Soc. 36, 221–230 (1961)
Volkmann, L.: Edge connectivity in \(p\)-partite graphs. J. Graph Theory 13(1), 1–6 (1989)
West, D., Wu, H.: Packing Steiner trees and \(S\)-connectors in graphs. J. Comb. Theory Ser. B 102, 186–205 (2012)
Xu, J., Yang, C.: Connectivity of Cartesian product graphs. Discrete Math. 306, 159–165 (2006)
Yang, C., Xu, J.: Connectivity of lexicographic product and direct product of graphs. Ars Comb. 111, 3–12 (2013)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Li, X., Yue, J., Zhao, Y. (2014). The Generalized 3-Edge-Connectivity of Lexicographic Product Graphs. In: Zhang, Z., Wu, L., Xu, W., Du, DZ. (eds) Combinatorial Optimization and Applications. COCOA 2014. Lecture Notes in Computer Science(), vol 8881. Springer, Cham. https://doi.org/10.1007/978-3-319-12691-3_31
Download citation
DOI: https://doi.org/10.1007/978-3-319-12691-3_31
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-12690-6
Online ISBN: 978-3-319-12691-3
eBook Packages: Computer ScienceComputer Science (R0)