Displaying similar documents to “Vertex-disjoint stars in graphs”

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...

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.

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...

The cobondage number of a graph

V.R. Kulli, B. Janakiram (1996)

Discussiones Mathematicae Graph Theory

Similarity:

A set D of vertices in a graph G = (V,E) is a dominating set of G if every vertex in V-D is adjacent to some vertex in D. The domination number γ(G) of G is the minimum cardinality of a dominating set. We define the cobondage number b c ( G ) of G to be the minimum cardinality among the sets of edges X ⊆ P₂(V) - E, where P₂(V) = X ⊆ V:|X| = 2 such that γ(G+X) < γ(G). In this paper, the exact values of bc(G) for some standard graphs are found and some bounds are obtained. Also, a Nordhaus-Gaddum...

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...

Radio number for some thorn graphs

Ruxandra Marinescu-Ghemeci (2010)

Discussiones Mathematicae Graph Theory

Similarity:

For a graph G and any two vertices u and v in G, let d(u,v) denote the distance between u and v and let diam(G) be the diameter of G. A multilevel distance labeling (or radio labeling) for G is a function f that assigns to each vertex of G a positive integer such that for any two distinct vertices u and v, d(u,v) + |f(u) - f(v)| ≥ diam(G) + 1. The largest integer in the range of f is called the span of f and is denoted span(f). The radio number of G, denoted rn(G), is the minimum span...