Bondage Numbers of C4 Bundles over a Cycle Cn

Abstract

Graph bundles generalize the notion of covering graphs and graph products. Graph bundles have been applied in computer architecture and communication networks. The bondage number is an important parameter for measuring the vulnerability and stability of the network domination under link failure. The bondage number b(G) of a graph G is the minimum number of edges whose removal enlarges the domination number. In this paper, we show that the bondage number of every C4 bundles over a cycle Cn (n≥4) is equal to 4.