2024/01/29 by E. G. K. M. Gamlath, Gamlath, E. G. K. M., Bing Wei +1
Computer Science · Engineering · #05C35 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #G.2.2 #Graph Labeling and Dimension Problems #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2401.16615
openalex publication_date 2024/01/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, we explore the concept of total bondage in finite graphs without isolated vertices. A vertex set D is considered a total dominating set if every vertex v in the graph G has a neighbor in D. The minimum cardinality of all total dominating sets in G is denoted as γt(G). A total bondage edge set B is a subset of the edges of G such that the removal of B from G does not create isolated vertices, and the total dominating number of the resulting graph G-B is strictly greater than γt(G). The total bondage number of G, denoted bt(G), is defined as the minimum cardinality of such total bondage edge sets. Our paper establishes upper bounds on bt(G) based on the maximum degree of a graph. Notably, for planar graphs with minimum degree δ(G) ≥ 3, we prove bt(G) ≤ Δ+ 8 or bt(G) ≤ 10. Additionally, for a connected planar graph with δ(G) ≥ 3 and g(G) ≥ 4, we show that bt(G) ≤ Δ+ 3 if G does not contain an edge with degree sum at most 7. We also improve some upper bounds of the total bondage number for trees, enhance existing lemmas, and find upper bounds for total bondage in specific graph classes.