The total bondage number of grid graphs

DOI10.1016/J.DAM.2012.06.012zbMATH Open1252.05163arXiv1109.3929OpenAlexW1983148984MaRDI QIDQ714029FDOQ714029

Authors: Fu-Tao Hu, You Lu, Jun-Ming Xu 

Publication date: 19 October 2012

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

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})$.

Full work available at URL: https://arxiv.org/abs/1109.3929

Recommendations

• Bondage number of grid graphs
• On the total domination subdivision numbers of grid graphs
• Total bondage number of a graph
• scientific article; zbMATH DE number 5759533
• Some progress on total bondage in graphs

zbMATH Keywords

total dominating settotal domination numbergrid graphstotal bondage number

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Total domination in graphs
• On the complexity of the bondage and reinforcement problems
• Theory and Application of Graphs
• Graphs with large total domination number
• A survey of selected recent results on total domination in graphs
• The bondage number of a graph
• Bounds on the bondage number of a graph
• New results about the bondage number of a graph
• Total domination number of grid graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Restrained bondage in graphs
• Bondage number of planar graphs
• Remarks on the bondage number of planar graphs
• The bondage numbers and efficient dominations of vertex-transitive graphs
• On the bondage number of planar and directed graphs
• The bondage and connectivity of a graph
• The total domination and total bondage numbers of extended de Bruijn and Kautz digraphs
• Total bondage number of a graph
• Bondage number of the discrete torus \(C_n\times C_4\)
• The bondage numbers of extended de Bruijn and Kautz digraphs
• The bondage numbers of graphs with small crossing numbers
• \(\alpha_k\)- and \(\gamma_k\)-stable graphs
• THE BONDAGE NUMBER OF C₃×C_n

Cited In (11)

• Bondage number of grid graphs
• Semitotal bondage numbers of graphs
• Some progress on total bondage in graphs
• Some classifications of graphs with respect to a set adjacency relation
• Bondage numbers of Mycielski graphs
• Title not available (Why is that?)
• On bondage numbers of graphs: a survey with some comments
• Hamiltonian cycles in linear-convex supergrid graphs
• The Hamiltonian properties of supergrid graphs
• NP-hardness of multiple bondage in graphs
• The total bondage numbers and efficient total dominations of vertex-transitive graphs

This page was built for publication: The total bondage number of grid graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q714029)