The Restricted Edge-Connectivity of Kronecker Product Graphs
Abstract
The restricted edge-connectivity of a connected graph , denoted by , if exists, is the minimum number of edges whose deletion disconnects the graph such that each connected component has at least two vertices. The Kronecker product of graphs and , denoted by , is the graph with vertex set , where two vertices and are adjacent in if and only if and . In this paper, it is proved that for any graph and a complete graph with vertices, where is minimum edge-degree of , and a sufficient condition such that is -optimal is acquired.
References
- 1. , Independent sets in tensor graph powers, J. Graph Theory 54 (2007) 73–87. Crossref, ISI, Google Scholar
- 2. , Graph Theory,
GTM244 (Springer, 2008). Crossref, Google Scholar - 3. , Some remarks on the Kronecker product of graphs, Inform. Process. Lett. 68 (1998) 55–61. Crossref, ISI, Google Scholar
- 4. , Hypercubes as direct products, SIAM J. Discrete Math. 18 (2005) 778–786. Crossref, ISI, Google Scholar
- 5. , Edge-connectivity of strong products of graphs, Discuss. Math. Graph Theory 27 (2007) 333–343. Crossref, Google Scholar
- 6. , On the connectivity of the direct product of graphs, Australas. J. Combin. 1 (2008) 45–56. Google Scholar
- 7. , On edge-connectivity of direct products of graphs, Inform. Process. Lett. 111 (2011) 899–902. Crossref, ISI, Google Scholar
- 8. , Computing the bipartite edge frustration of fullerene graphs, Discrete Appl. Math. 155 (2007) 1294–1301. Crossref, ISI, Google Scholar
- 9. , On computing a conditional edge-connectivity of a graph, Inform. Process. Lett. 27 (1988) 195–199. Crossref, ISI, Google Scholar
- 10. , A finite automata approach to modeling the cross product of interconnection networks, Math. Comput. Model. 30 (1999) 185–200. Crossref, ISI, Google Scholar
- 11. , A note on the connectivity of Kronecker products of graphs, Appl. Math. Lett. 22 (2009) 1360–1363. Crossref, ISI, Google Scholar
- 12. , Network bipartivity, Phys. Rev. E 68 (2003) 056107. Crossref, ISI, Google Scholar
- 13. , Product Graphs: Structure and Recognition (Wiley, 2000). Google Scholar
- 14. , On the edge-connectivity of Cartesian product graphs, Asian-Eur. J. Math. 1 (2008) 93–98. Link, Google Scholar
- 15. , Products of graphs and applications, Modeling and Simulation 5 (1974) 1119–1123. Google Scholar
- 16. , Reliability analysis of circulant graphs, Networks 31 (1998) 61–65. Crossref, ISI, Google Scholar
- 17. , Vertex vulnerability parameters of Kronecker product of complete graphs, Inform. Process. Lett. 106 (2008) 258–262. Crossref, ISI, Google Scholar
- 18. , Double graphs, Discrete Math. 308 (2008) 242–254. Crossref, ISI, Google Scholar
- 19. , Connectivity of Cartesian products of graphs, Appl. Math. Lett. 21 (2008) 682–685. Crossref, ISI, Google Scholar
- 20. , Connectivity of strong products of graphs, Graphs Combin. 26 (2010) 457–467. Crossref, ISI, Google Scholar
- 21. , Connectivity of Cartesian products of graphs, Discrete Math. 306 (2006) 159–165. Crossref, ISI, Google Scholar
- 22. , Connectivity and super-connectivity of Cartesian product graphs, Ars Combin. 95 (2010) 235–245. Google Scholar
- 23. , Reliability of interconnection networks modeled by Cartesian product graphs, Networks 52(4) (2008) 202–205. Crossref, ISI, Google Scholar
- 24. , Connectivity of lexicographic product and direct product of graphs, Ars Combin. 111 (2013) 3–12. ISI, Google Scholar


