The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

Displaying similar documents to “Bounds concerning the alliance number”

The independent resolving number of a graph

Gary Chartrand, Varaporn Saenpholphat, Ping Zhang (2003)

Mathematica Bohemica

Similarity:

For an ordered set W = { w 1 , w 2 , ⋯ , w k } of vertices in a connected graph G and a vertex v of G , the code of v with respect to W is the k -vector c W ( v ) = ( d ( v , w 1 ) , d ( v , w 2 ) , ⋯ , d ( v , w k ) ) . The set W is an independent resolving set for G if (1) W is independent in G and (2) distinct vertices have distinct codes with respect to W . The cardinality of a minimum independent resolving set in G is the independent resolving number i r ( G ) . We study the existence of independent resolving sets in graphs, characterize all nontrivial connected graphs G of order...

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.

On domination number of 4-regular graphs

Hailong Liu, Liang Sun (2004)

Czechoslovak Mathematical Journal

Similarity:

Let G be a simple graph. A subset S ⊆ V is a dominating set of G , if for any vertex v ∈ V - S there exists a vertex u ∈ S such that u v ∈ E ( G ) . The domination number, denoted by γ ( G ) , is the minimum cardinality of a dominating set. In this paper we prove that if G is a 4-regular graph with order n , then γ ( G ) ≤ 4 11 n .

Vertex-disjoint stars in graphs

Katsuhiro Ota (2001)

Discussiones Mathematicae Graph Theory

Similarity:

In this paper, we give a sufficient condition for a graph to contain vertex-disjoint stars of a given size. It is proved that if the minimum degree of the graph is at least k+t-1 and the order is at least (t+1)k + O(t²), then the graph contains k vertex-disjoint copies of a star K 1 , t . The condition on the minimum degree is sharp, and there is an example showing that the term O(t²) for the number of uncovered vertices is necessary in a sense.