World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

The Restricted Edge-Connectivity of Kronecker Product Graphs

    The restricted edge-connectivity of a connected graph G, denoted by λ(G), 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 G and H, denoted by G×H, is the graph with vertex set V(G×H)=V(G)×V(H), where two vertices (u1,v1) and (u2,v2) are adjacent in G×H if and only if u1u2E(G) and v1v2E(H). In this paper, it is proved that λ(G×Kn)=min{(n1)ξ(G)+2(n2),n(n1)λ(G)} for any graph G and a complete graph Kn with n3 vertices, where ξ(G) is minimum edge-degree of G, and a sufficient condition such that G×Kn is λ-optimal is acquired.

    References

    • 1. N. Alon and E. Lubetzky, Independent sets in tensor graph powers, J. Graph Theory 54 (2007) 73–87. Crossref, ISIGoogle Scholar
    • 2. J. A. Bondy and U. S. R. Murty, Graph Theory, GTM244 (Springer, 2008). CrossrefGoogle Scholar
    • 3. A. Bottreou and Y. Métivier, Some remarks on the Kronecker product of graphs, Inform. Process. Lett. 68 (1998) 55–61. Crossref, ISIGoogle Scholar
    • 4. B. Brešr et al., Hypercubes as direct products, SIAM J. Discrete Math. 18 (2005) 778–786. Crossref, ISIGoogle Scholar
    • 5. B. Brešr and S. Špacapan, Edge-connectivity of strong products of graphs, Discuss. Math. Graph Theory 27 (2007) 333–343. CrossrefGoogle Scholar
    • 6. B. Brešr and S. Špacapan, On the connectivity of the direct product of graphs, Australas. J. Combin. 1 (2008) 45–56. Google Scholar
    • 7. X.-L. Cao and S. Brglez, On edge-connectivity of direct products of graphs, Inform. Process. Lett. 111 (2011) 899–902. Crossref, ISIGoogle Scholar
    • 8. T. Došlić and D. Vukičević, Computing the bipartite edge frustration of fullerene graphs, Discrete Appl. Math. 155 (2007) 1294–1301. Crossref, ISIGoogle Scholar
    • 9. A. H. Esfahanian and S. L. Hakimi, On computing a conditional edge-connectivity of a graph, Inform. Process. Lett. 27 (1988) 195–199. Crossref, ISIGoogle Scholar
    • 10. S. A. Ghozati, A finite automata approach to modeling the cross product of interconnection networks, Math. Comput. Model. 30 (1999) 185–200. Crossref, ISIGoogle Scholar
    • 11. R. Guji and E. Vumar, A note on the connectivity of Kronecker products of graphs, Appl. Math. Lett. 22 (2009) 1360–1363. Crossref, ISIGoogle Scholar
    • 12. P. Holme et al., Network bipartivity, Phys. Rev. E 68 (2003) 056107. Crossref, ISIGoogle Scholar
    • 13. W. Imrich and S. Klavžar, Product Graphs: Structure and Recognition (Wiley, 2000). Google Scholar
    • 14. S. Klavžar and S. Špacapan, On the edge-connectivity of Cartesian product graphs, Asian-Eur. J. Math. 1 (2008) 93–98. LinkGoogle Scholar
    • 15. R. H. Lammprey and B. H. Barnes, Products of graphs and applications, Modeling and Simulation 5 (1974) 1119–1123. Google Scholar
    • 16. Q. Li and Q. Li, Reliability analysis of circulant graphs, Networks 31 (1998) 61–65. Crossref, ISIGoogle Scholar
    • 17. A. Mamut and E. Vumar, Vertex vulnerability parameters of Kronecker product of complete graphs, Inform. Process. Lett. 106 (2008) 258–262. Crossref, ISIGoogle Scholar
    • 18. E. Munarini et al., Double graphs, Discrete Math. 308 (2008) 242–254. Crossref, ISIGoogle Scholar
    • 19. S. Špacapan, Connectivity of Cartesian products of graphs, Appl. Math. Lett. 21 (2008) 682–685. Crossref, ISIGoogle Scholar
    • 20. S. Špacapan, Connectivity of strong products of graphs, Graphs Combin. 26 (2010) 457–467. Crossref, ISIGoogle Scholar
    • 21. J. M. Xu and C. Yang, Connectivity of Cartesian products of graphs, Discrete Math. 306 (2006) 159–165. Crossref, ISIGoogle Scholar
    • 22. J. M. Xu and C. Yang, Connectivity and super-connectivity of Cartesian product graphs, Ars Combin. 95 (2010) 235–245. Google Scholar
    • 23. C. Yang and J. M. Xu, Reliability of interconnection networks modeled by Cartesian product graphs, Networks 52(4) (2008) 202–205. Crossref, ISIGoogle Scholar
    • 24. C. Yang and J. M. Xu, Connectivity of lexicographic product and direct product of graphs, Ars Combin. 111 (2013) 3–12. ISIGoogle Scholar