Toughness of the corona of two graphs

Abstract

The toughness of a non-complete graph G=(V, E) is defined as τ(G)=min{|S|/ω(G−S)}, where the minimum is taken over all cutsets S of vertices of G and ω(G−S) denotes the number of components of the resultant graph G−S by deletion of S. The corona of two graphs G and H, written as G° H, is the graph obtained by taking one copy of G and |V(G)| copies of H, and then joining the ith vertex of G to every vertex in the ith copy of H. In this paper, we investigate the toughness of this kind of graphs and obtain the exact value for the corona of two graphs belonging to some families as paths, cycles, stars, wheels or complete graphs.

Keywords:

• connectivity
• toughness
• networks
• vulnerability

2000 AMS Subject Classifications :

• 05C35
• 05C40

Acknowledgements

We want to deeply thank the anonymous referees who helped us to improve this paper. This research was supported by the Ministry of Education and Science, Spain, and the European Regional Development Fund (ERDF) under project MTM2008-06620-C03-02/MTM, Catalonian Government 1298 SGR2009 and by the Andalusian Government under project P06-FQM-01649.