The total bondage number of grid graphs

2011/09/19 by Fu-Tao Hu, Hu, Fu-Tao, You Lu +4
Computer Science · Mathematics · #05C12 #05C25 #05C40 #Advanced Graph Theory Research #Combinatorics (math.CO) #E.1 #FOS: Mathematics #G.2.2 #Graph Labeling and Dimension Problems #Interconnection Networks and Systems #acm:05C12 #acm:05C25 #acm:05C40 #math.CO #msc:05C12 #msc:05C25 #msc:05C40

paper · pdf · doi:10.48550/arxiv.1109.3929

15 pages with 4 figures

arxiv created 2011/09/19 · openalex publication_date 2011/09/19 · arxiv updated 2011/09/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The total domination number of a graph G without isolated vertices is the minimum number of vertices that dominate all vertices in G. The total bondage number b_t(G) of G is the minimum number of edges whose removal enlarges the total domination number. This paper considers grid graphs. An (n,m)-grid graph G_n,m is defined as the cartesian product of two paths P_n and P_m. This paper determines the exact values of b_t(G_n,2) and b_t(G_n,3), and establishes some upper bounds of b_t(G_n,4).

Related

• The k-Total Bondage Number of a Graph
• On Total Bondage Number of Graphs
• The Bondage Number of Mesh Networks
• The 2-Domination and 2-Bondage Numbers of Grid Graphs
• The bondage number of random graphs