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.

Homogeneously embedding stratified graphs in stratified graphs

Gary Chartrand, Donald W. Vanderjagt, Ping Zhang (2005)

Mathematica Bohemica

Similarity:

A 2-stratified graph G is a graph whose vertex set has been partitioned into two subsets, called the strata or color classes of G . Two 2 -stratified graphs G and H are isomorphic if there exists a color-preserving isomorphism φ from G to H . A 2 -stratified graph G is said to be homogeneously embedded in a 2 -stratified graph H if for every vertex x of G and every vertex y of H , where x and y are colored the same, there exists an induced 2 -stratified subgraph H ' of H containing y and a color-preserving...