The Bondage Number of Mesh Networks

2011/09/19 by Hu, Fu-Tao, Cao, Yong-Chang, Xu, Jun-Ming
#05C12 #05C25 #05C40 #05C69 #Combinatorics (math.CO) #E.1 #FOS: Mathematics #G.2.2

paper · doi:10.48550/arxiv.1109.3927

Abstract

The bondage number b(G) of a nonempty graph G is the smallest number of edges whose removal from G results in a graph with domination number greater than that of G. Denote P_n× P_m be the Cartesian product of two paths P_n and P_m. This paper determines that the exact value of b(P_n× P₂), b(P_n× P₃) and b(P_n× P₄) for n≥ 2.

Related

• The total bondage number of grid graphs
• Note on the bondage number of graphs on topological surfaces
• Generalized Bondage Number: The k-synchronous bondage number of a graph
• On Bondage Numbers of Graphs -- a survey with some comments
• The bondage number of random graphs