Path-connectivity of lexicographic product graphs

References

• F. Bao, Y. Igarashi, and S.R. Öhring, Reliable broadcasting in product networks, Discret. Appl. Math. 83 (1998), pp. 3–20. doi: 10.1016/S0166-218X(97)00100-5
   Web of Science ®Google Scholar
• L.W. Beineke and R.J. Wilson, Topics in Structural Graph Theory, Cambridge University Press, Cambridge, 2013.
   Google Scholar
• A. Blasiak, R. Kleinberg, and E. Lubetzky, Lexicographic products and the power of non-linear network coding, 2013. arXiv: 1108.2489 [math.CO].
   Google Scholar
• J.A. Bondy and U.S.R. Murty, Graph Theory, Graduate Texts in Mathematics, Springer, New York, 2008.
   Google Scholar
• N.J. Calkin and H.S. Wilf, The number of independent sets in a grid graph, SIAM J. Discret. Math.11(1) (1998), pp. 54–60. doi: 10.1137/S089548019528993X
   Web of Science ®Google Scholar
• G. Chartrand, S.F. Kappor, L. Lesniak, and D.R. Lick, Generalized connectivity in graphs, Bull. Bombay Math. Colloq. 2 (1984), pp. 1–6.
   Google Scholar
• G. Chartrand, F. Okamoto, and P. Zhang, Rainbow trees in graphs and generalized connectivity, Networks 55(4) (2010), pp. 360–367.
   Web of Science ®Google Scholar
• X. Cheng and D. Du, Steiner Trees in Industry, Kluwer Academic Publisher, Dordrecht, 2001.
   Google Scholar
• S.K. Das, S.R. Öhring, and A.K. Banerjee, Embeddings into hyper Petersen networks: Yet another hypercube-like interconnection topology, VLSI Design 2(4) (1995), pp. 335–351. doi: 10.1155/1995/95759
   Web of Science ®Google Scholar
• K. Day and A.-E. Al-Ayyoub, The cross product of interconnection networks, IEEE Trans. Parallel Distrib. Syst. 8(2) (1997), pp. 109–118. doi: 10.1109/71.577251
   Web of Science ®Google Scholar
• D.P. Day, O.R. Oellermann, and H.C. Swart, The ℓ-connectivity function of trees and complete multipartite graphs, J. Combin. Math. Combin. Comput. 10 (1991), pp. 183–192.
   Google Scholar
• G.A. Dirac, In abstrakten Graphen vorhandene vollständige 4-Graphen und ihre Unterteilungen, Math. Nach 22 (1960), pp. 61–85. doi: 10.1002/mana.19600220107
   Google Scholar
• D. Du and X. Hu, Steiner Tree Problems in Computer Communication Networks, World Scientific, Singapore, 2008.
   Google Scholar
• M. Feng, M. Xu, and K. Wang, Identifying codes of lexicographic product of graphs, Electron. J. Combin. 19(4) (2012), pp. 56–63.
   Google Scholar
• P. Fragopoulou and S.G. Akl, Edge-disjoint spanning trees on the star network with applications to fault tolerance, IEEE Trans. Comput. 45(2) (1996), pp. 174–185. doi: 10.1109/12.485370
   Web of Science ®Google Scholar
• M. Grötschel, The Steiner tree packing problem in V LSI design, Math. Program. 78 (1997), pp. 265–281. doi: 10.1007/BF02614374
   Web of Science ®Google Scholar
• M. Grötschel, A. Martin, and R. Weismantel, Packing Steiner trees: A cutting plane algorithm and computational results, Math. Program. 72 (1996), pp. 125–145. doi: 10.1007/BF02592086
   Web of Science ®Google Scholar
• M. Hager, Pendant tree-connectivity, J. Comb. Theory, Ser. B 38 (1985), pp. 179–189. doi: 10.1016/0095-8956(85)90083-8
   Web of Science ®Google Scholar
• M. Hager, Path-connectivity in graphs, Discret. Math. 59 (1986), pp. 53–59. doi: 10.1016/0012-365X(86)90068-3
   Web of Science ®Google Scholar
• R. Hammack, W. Imrich, and S. Klavr, Handbook of Product Graphs, 2nd ed., CRC Press, New York, 2011.
   Google Scholar
• S.M. Hedetniemi, S.T. Hedetniemi, and A.L. Liestman, A survey of gossiping and broadcasting in communication networks, Networks 18 (1988), pp. 1240–1268. doi: 10.1002/net.3230180406
   Web of Science ®Google Scholar
• A. Itai, C.H. Papadimitriou, and J.L. Szwarcfiter, Hamilton paths in grid graphs, SIAM J. Comput.11(4) (1982), pp. 676–686. doi: 10.1137/0211056
   Web of Science ®Google Scholar
• P. Jalote, Fault Tolerance in Distributed Systems, Prentice-Hall, Englewood Cliffs, NJ, 1994.
   Google Scholar
• S. Ku, B. Wang, and T. Hung, Constructing edge-disjoint spanning trees in product networks, IEEE Trans Parallel Distrib Syst. 14(3) (2003), pp. 213–221. doi: 10.1109/TPDS.2003.1189580
   Web of Science ®Google Scholar
• S. Li and X. Li, Note on the hardness of generalized connectivity, J. Combin. Optimiz. 24 (2012), pp. 389–396. doi: 10.1007/s10878-011-9399-x
   Web of Science ®Google Scholar
• X. Li and Y. Mao, On extremal graphs with at most ℓ internally disjoint Steiner trees connecting any n−1 vertices, accepted by Graphs & Combin.
   Google Scholar
• X. Li and Y. Mao, The generalied 3-connectivity of lexigraphical product graphs, Discret. Math. Theor. Comput. Sci. 16(1) (2014), pp. 339–354.
   Google Scholar
• S. Li, X. Li, and W. Zhou, Sharp bounds for the generalized connectivity κ3(G), Discret. Math. 310 (2010), pp. 2147–2163. doi: 10.1016/j.disc.2010.04.011
   Web of Science ®Google Scholar
• F. Li, Z. Xu, H. Zhao, and W. Wang, On the number of spanning trees of the lexicographic product of networks, Sci. China, Ser. F 42 (2012), pp. 949–959.
   Google Scholar
• H. Li, X. Li, and Y. Sun, The generalised 3-connectivity of Cartesian product graphs, Discret. Math. Theor. Comput. Sci. 14(1) (2012), pp. 43–54. doi: 10.1016/j.commatsci.2011.09.003
   Web of Science ®Google Scholar
• H. Li, X. Li, and Y. Mao, On extremal graphs with at most two internally disjoint Steiner trees connecting any three vertices, Bull. Malays. Math. Sci. Soc. (2) 37(3) (2014), pp. 747–756.
   Web of Science ®Google Scholar
• X. Li, Y. Mao, and Y. Sun, On the generalized (edge-)connectivity of graphs, Aust. J. Combin. 58(2) (2014), pp. 304–319.
   Google Scholar
• O.R. Oellermann, On the ℓ-connectivity of a graph, Graphs Combin. 3 (1987), pp. 285–291. doi: 10.1007/BF01788551
   Web of Science ®Google Scholar
• O.R. Oellermann, A note on the ℓ-connectivity function of a graph, Congessus Numerantium 60 (1987), pp. 181–188.
   Google Scholar
• O.R. Oellermann, Connectivity and edge-connectivity in graphs: A survey, Congessus Numerantium116 (1996), pp. 231–252.
   Google Scholar
• F. Okamoto and P. Zhang, The tree connectivity of regular complete bipartite graphs, J. Combin. Math. Combin. Comput. 74 (2010), pp. 279–293.
   Google Scholar
• K. Ozeki and T. Yamashita, Spanning trees: A survey, Graphs Combin. 27(1) (2011), pp. 1–26. doi: 10.1007/s00373-010-0973-2
   Web of Science ®Google Scholar
• E.M. Palmer, On the spanning tree packing number of a graph: a survey, Discret. Math. 230 (2001), pp. 13–21. doi: 10.1016/S0012-365X(00)00066-2
   Web of Science ®Google Scholar
• P. Ramanathan, D.D. Kandlur, and K.G. Shin, Hardware-assisted software clock synchronization for homogeneous distributed systems, IEEE Trans. Comput. 39 (1990), pp. 514–524. doi: 10.1109/12.54844
   Web of Science ®Google Scholar
• N.A. Sherwani, Algorithms for V LSI Physical Design Automation, 3rd ed., Kluwer Acad. Pub., London, 1999.
   Google Scholar
• D. West, Introduction to Graph Theory, 2nd ed., Prentice-Hall, New Jersey, 2001.
   Google Scholar
• E.L. Wilson, R.L. Hemminger, and M.D. Plimmer, A family of path properties for graphs, Math. Ann.197 (1972), pp. 107–122. doi: 10.1007/BF01419587
   Web of Science ®Google Scholar
• C. Yang and J. Xu, Connectivity of lexicographic product and direct product of graphs, Ars Combin.111 (2013), pp. 3–12.
   Web of Science ®Google Scholar