2022/03/17 by Valentin Bouquet, Bouquet, Valentin
Computer Science · Neuroscience · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Interconnection Networks and Systems #Nuclear Receptors and Signaling
paper · pdf · doi:10.48550/arxiv.2203.09256
openalex publication_date 2022/03/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A set S⊆ V(G) of a graph G is a dominating set if each vertex has a neighbor in S or belongs to S. Let γ(G) be the cardinality of a minimum dominating set in G. The bondage number b(G) of a graph G is the smallest cardinality of a set edges A⊆ E(G) such that γ(G-A)=γ(G)+1. A chordal graph is a graph with no induced cycle of length four or more. In this paper, we prove that the bondage number of a chordal graph G is at most the order of its maximum clique, that is, b(G)≤ ω(G). We show that this bound is best possible.