New results about the bondage number of a graph (Q1363706)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | New results about the bondage number of a graph |
scientific article |
Statements
New results about the bondage number of a graph (English)
0 references
8 September 1997
0 references
Let \(G=(V,E)\) be a simple graph. A set \(D\) is called a dominating set if for any vertex \(u\) in \(V\) there is a vertex \(v\) in \(D\) such that \(uv\) is an edge in \(E\). A dominating set of minimum cardinality in \(G\) is called minimum dominating set, and its cardinality is called the domination number of \(G\) (denoted by \(\gamma(G)\)). The bondage number \(b(G)\) of a nonempty graph is the minimum cardinality among all sets of edges \(X\) for which \(\gamma(G- X)>\gamma(G)\) holds. The author presents a characterization of those trees having bondage number 1. He also obtains results on the lower bounds for the bondage number and some new sharp upper bounds.
0 references
dominating set
0 references
domination number
0 references
bondage number
0 references
characterization
0 references
trees
0 references