Displaying similar documents to “The independent resolving number of a graph”

Bounds concerning the alliance number

Grady Bullington, Linda Eroh, Steven J. Winters (2009)

Mathematica Bohemica

Similarity:

P. Kristiansen, S. M. Hedetniemi, and S. T. Hedetniemi, in Alliances in graphs, J. Combin. Math. Combin. Comput. 48 (2004), 157–177, and T. W. Haynes, S. T. Hedetniemi, and M. A. Henning, in Global defensive alliances in graphs, Electron. J. Combin. 10 (2003), introduced the defensive alliance number a ( G ) , strong defensive alliance number a ^ ( G ) , and global defensive alliance number γ a ( G ) . In this paper, we consider relationships between these parameters and the domination number γ ( G ) . For any positive...

Resolving domination in graphs

Robert C. Brigham, Gary Chartrand, Ronald D. Dutton, Ping Zhang (2003)

Mathematica Bohemica

Similarity:

For an ordered set W = { w 1 , w 2 , ⋯ , w k } of vertices and a vertex v in a connected graph G , the (metric) representation of v with respect to W is the k -vector r ( v | W ) = ( d ( v , w 1 ) , d ( v , w 2 ) , ⋯ , d ( v , w k ) ) , where d ( x , y ) represents the distance between the vertices x and y . The set W is a resolving set for G if distinct vertices of G have distinct representations with respect to W . A resolving set of minimum cardinality is called a minimum resolving set or a basis and the cardinality of a basis for G is its dimension dim G . A set S of vertices in G is a dominating...

A bound on the k -domination number of a graph

Lutz Volkmann (2010)

Czechoslovak Mathematical Journal

Similarity:

Let G be a graph with vertex set V ( G ) , and let k ≥ 1 be an integer. A subset D ⊆ V ( G ) is called a if every vertex v ∈ V ( G ) - D has at least k neighbors in D . The k -domination number γ k ( G ) of G is the minimum cardinality of a k -dominating set in G . If G is a graph with minimum degree δ ( G ) ≥ k + 1 , then we prove that γ k + 1 ( G ) ≤ | V ( G ) | + γ k ( G ) 2 . In addition, we present a characterization of a special class of graphs attaining equality in this inequality.