排序方式: 共有5条查询结果,搜索用时 15 毫秒
1
1.
For any positive integer n and any graph G a set D of vertices of G is a distance-n dominating set, if every vertex vV(G)−D has exactly distance n to at least one vertex in D. The distance-n domination number γ=n(G) is the smallest number of vertices in any distance-n dominating set. If G is a graph of order p and each vertex in G has distance n to at least one vertex in G, then the distance-n domination number has the upper bound p/2 as Ore's upper bound on the classical domination number. In this paper, a characterization is given for graphs having distance-n domination number equal to half their order, when the diameter is greater or equal 2n−1. With this result we confirm a conjecture of Boland, Haynes, and Lawson. 相似文献
2.
Maximum graphs with a unique minimum dominating set 总被引:2,自引:0,他引:2
We present a conjecture on the maximum number of edges of a graph that has a unique minimum dominating set. We verify our conjecture for some special cases and prove a weakened version of this conjecture in general. 相似文献
3.
Block graphs with unique minimum dominating sets 总被引:1,自引:0,他引:1
Miranca Fischermann 《Discrete Mathematics》2001,240(1-3):247-251
For any graph G a set D of vertices of G is a dominating set, if every vertex vV(G)−D has at least one neighbor in D. The domination number γ(G) is the smallest number of vertices in any dominating set. In this paper, a characterization is given for block graphs having a unique minimum dominating set. With this result, we generalize a theorem of Gunther, Hartnell, Markus and Rall for trees. 相似文献
4.
Remarks on the bondage number of planar graphs 总被引:4,自引:0,他引:4
The bondage number b(G) of a nonempty graph G is the cardinality of a smallest set of edges whose removal from G results in a graph with domination number greater than the domination number γ(G) of G. In 1998, J.E. Dunbar, T.W. Haynes, U. Teschner, and L. Volkmann posed the conjecture b(G)Δ(G)+1 for every nontrivial connected planar graph G. Two years later, L. Kang and J. Yuan proved b(G)8 for every connected planar graph G, and therefore, they confirmed the conjecture for Δ(G)7. In this paper we show that this conjecture is valid for all connected planar graphs of girth g(G)4 and maximum degree Δ(G)5 as well as for all not 3-regular graphs of girth g(G)5. Some further related results and open problems are also presented. 相似文献
5.
Miranca?Fischermann Werner?Knoben Dirk?Kremer Dieter?RautenbachEmail author 《Order》2004,21(2):131-135
We prove that a finite poset P=(V,≤) is determined up to some permutation of its elements by the function
defined by mP({u,v})=|{w∈V∣u≤w and v≤w}|. 相似文献
1