Displaying similar documents to “A remark on the (2,2)-domination number”

Domination Subdivision Numbers

Teresa W. Haynes, Sandra M. Hedetniemi, Stephen T. Hedetniemi, David P. Jacobs, James Knisely, Lucas C. van der Merwe (2001)

Discussiones Mathematicae Graph Theory

Similarity:

A set S of vertices of a graph G = (V,E) is a dominating set if every vertex of V-S is adjacent to some vertex in S. The domination number γ(G) is the minimum cardinality of a dominating set of G, and the domination subdivision number s d γ ( G ) is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the domination number. Arumugam conjectured that 1 s d γ ( G ) 3 for any graph G. We give a counterexample to this conjecture. On the other hand,...

Roman bondage in graphs

Nader Jafari Rad, Lutz Volkmann (2011)

Discussiones Mathematicae Graph Theory

Similarity:

A Roman dominating function on a graph G is a function f:V(G) → 0,1,2 satisfying the condition that every vertex u for which f(u) = 0 is adjacent to at least one vertex v for which f(v) = 2. The weight of a Roman dominating function is the value f ( V ( G ) ) = u V ( G ) f ( u ) . The Roman domination number, γ R ( G ) , of G is the minimum weight of a Roman dominating function on G. In this paper, we define the Roman bondage b R ( G ) of a graph G with maximum degree at least two to be the minimum cardinality of all sets E’ ⊆ E(G)...

Full domination in graphs

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

Discussiones Mathematicae Graph Theory

Similarity:

For each vertex v in a graph G, let there be associated a subgraph H v of G. The vertex v is said to dominate H v as well as dominate each vertex and edge of H v . A set S of vertices of G is called a full dominating set if every vertex of G is dominated by some vertex of S, as is every edge of G. The minimum cardinality of a full dominating set of G is its full domination number γ F H ( G ) . A full dominating set of G of cardinality γ F H ( G ) is called a γ F H -set of G. We study three types of full domination in...

Graphs with large double domination numbers

Michael A. Henning (2005)

Discussiones Mathematicae Graph Theory

Similarity:

In a graph G, a vertex dominates itself and its neighbors. A subset S ⊆ V(G) is a double dominating set of G if S dominates every vertex of G at least twice. The minimum cardinality of a double dominating set of G is the double domination number γ × 2 ( G ) . If G ≠ C₅ is a connected graph of order n with minimum degree at least 2, then we show that γ × 2 ( G ) 3 n / 4 and we characterize those graphs achieving equality.

The geodetic number of strong product graphs

A.P. Santhakumaran, S.V. Ullas Chandran (2010)

Discussiones Mathematicae Graph Theory

Similarity:

For two vertices u and v of a connected graph G, the set I G [ u , v ] consists of all those vertices lying on u-v geodesics in G. Given a set S of vertices of G, the union of all sets I G [ u , v ] for u,v ∈ S is denoted by I G [ S ] . A set S ⊆ V(G) is a geodetic set if I G [ S ] = V ( G ) and the minimum cardinality of a geodetic set is its geodetic number g(G) of G. Bounds for the geodetic number of strong product graphs are obtainted and for several classes improved bounds and exact values are obtained.

On the total k-domination number of graphs

Adel P. Kazemi (2012)

Discussiones Mathematicae Graph Theory

Similarity:

Let k be a positive integer and let G = (V,E) be a simple graph. The k-tuple domination number γ × k ( G ) of G is the minimum cardinality of a k-tuple dominating set S, a set that for every vertex v ∈ V, | N G [ v ] S | k . Also the total k-domination number γ × k , t ( G ) of G is the minimum cardinality of a total k -dominating set S, a set that for every vertex v ∈ V, | N G ( v ) S | k . The k-transversal number τₖ(H) of a hypergraph H is the minimum size of a subset S ⊆ V(H) such that |S ∩e | ≥ k for every edge e ∈ E(H). We know that for...

Domination and independence subdivision numbers of graphs

Teresa W. Haynes, Sandra M. Hedetniemi, Stephen T. Hedetniemi (2000)

Discussiones Mathematicae Graph Theory

Similarity:

The domination subdivision number s d γ ( G ) of a graph is the minimum number of edges that must be subdivided (where an edge can be subdivided at most once) in order to increase the domination number. Arumugam showed that this number is at most three for any tree, and conjectured that the upper bound of three holds for any graph. Although we do not prove this interesting conjecture, we give an upper bound for the domination subdivision number for any graph G in terms of the minimum degrees of...

On locating-domination in graphs

Mustapha Chellali, Malika Mimouni, Peter J. Slater (2010)

Discussiones Mathematicae Graph Theory

Similarity:

A set D of vertices in a graph G = (V,E) is a locating-dominating set (LDS) if for every two vertices u,v of V-D the sets N(u)∩ D and N(v)∩ D are non-empty and different. The locating-domination number γ L ( G ) is the minimum cardinality of a LDS of G, and the upper locating-domination number, Γ L ( G ) is the maximum cardinality of a minimal LDS of G. We present different bounds on Γ L ( G ) and γ L ( G ) .

Paired domination in prisms of graphs

Christina M. Mynhardt, Mark Schurch (2011)

Discussiones Mathematicae Graph Theory

Similarity:

The paired domination number γ p r ( G ) of a graph G is the smallest cardinality of a dominating set S of G such that ⟨S⟩ has a perfect matching. The generalized prisms πG of G are the graphs obtained by joining the vertices of two disjoint copies of G by |V(G)| independent edges. We provide characterizations of the following three classes of graphs: γ p r ( π G ) = 2 γ p r ( G ) for all πG; γ p r ( K G ) = 2 γ p r ( G ) ; γ p r ( K G ) = γ p r ( G ) .

On double domination in graphs

Jochen Harant, Michael A. Henning (2005)

Discussiones Mathematicae Graph Theory

Similarity:

In a graph G, a vertex dominates itself and its neighbors. A subset S ⊆ V(G) is a double dominating set of G if S dominates every vertex of G at least twice. The minimum cardinality of a double dominating set of G is the double domination number γ × 2 ( G ) . A function f(p) is defined, and it is shown that γ × 2 ( G ) = m i n f ( p ) , where the minimum is taken over the n-dimensional cube C = p = ( p , . . . , p ) | p i I R , 0 p i 1 , i = 1 , . . . , n . Using this result, it is then shown that if G has order n with minimum degree δ and average degree d, then γ × 2 ( G ) ( ( l n ( 1 + d ) + l n δ + 1 ) / δ ) n .

On vertex stability with regard to complete bipartite subgraphs

Aneta Dudek, Andrzej Żak (2010)

Discussiones Mathematicae Graph Theory

Similarity:

A graph G is called (H;k)-vertex stable if G contains a subgraph isomorphic to H ever after removing any of its k vertices. Q(H;k) denotes the minimum size among the sizes of all (H;k)-vertex stable graphs. In this paper we complete the characterization of ( K m , n ; 1 ) -vertex stable graphs with minimum size. Namely, we prove that for m ≥ 2 and n ≥ m+2, Q ( K m , n ; 1 ) = m n + m + n and K m , n * K as well as K m + 1 , n + 1 - e are the only ( K m , n ; 1 ) -vertex stable graphs with minimum size, confirming the conjecture of Dudek and Zwonek.

A note on periodicity of the 2-distance operator

Bohdan Zelinka (2000)

Discussiones Mathematicae Graph Theory

Similarity:

The paper solves one problem by E. Prisner concerning the 2-distance operator T₂. This is an operator on the class C f of all finite undirected graphs. If G is a graph from C f , then T₂(G) is the graph with the same vertex set as G in which two vertices are adjacent if and only if their distance in G is 2. E. Prisner asks whether the periodicity ≥ 3 is possible for T₂. In this paper an affirmative answer is given. A result concerning the periodicity 2 is added.

Secure domination and secure total domination in graphs

William F. Klostermeyer, Christina M. Mynhardt (2008)

Discussiones Mathematicae Graph Theory

Similarity:

A secure (total) dominating set of a graph G = (V,E) is a (total) dominating set X ⊆ V with the property that for each u ∈ V-X, there exists x ∈ X adjacent to u such that ( X - x ) u is (total) dominating. The smallest cardinality of a secure (total) dominating set is the secure (total) domination number γ s ( G ) ( γ s t ( G ) ) . We characterize graphs with equal total and secure total domination numbers. We show that if G has minimum degree at least two, then γ s t ( G ) γ s ( G ) . We also show that γ s t ( G ) is at most twice the clique covering...

A note on the independent domination number versus the domination number in bipartite graphs

Shaohui Wang, Bing Wei (2017)

Czechoslovak Mathematical Journal

Similarity:

Let γ ( G ) and i ( G ) be the domination number and the independent domination number of G , respectively. Rad and Volkmann posted a conjecture that i ( G ) / γ ( G ) Δ ( G ) / 2 for any graph G , where Δ ( G ) is its maximum degree (see N. J. Rad, L. Volkmann (2013)). In this work, we verify the conjecture for bipartite graphs. Several graph classes attaining the extremal bound and graphs containing odd cycles with the ratio larger than Δ ( G ) / 2 are provided as well.

The vertex detour hull number of a graph

A.P. Santhakumaran, S.V. Ullas Chandran (2012)

Discussiones Mathematicae Graph Theory

Similarity:

For vertices x and y in a connected graph G, the detour distance D(x,y) is the length of a longest x - y path in G. An x - y path of length D(x,y) is an x - y detour. The closed detour interval ID[x,y] consists of x,y, and all vertices lying on some x -y detour of G; while for S ⊆ V(G), I D [ S ] = x , y S I D [ x , y ] . A set S of vertices is a detour convex set if I D [ S ] = S . The detour convex hull [ S ] D is the smallest detour convex set containing S. The detour hull number dh(G) is the minimum cardinality among subsets S of...

Algebraic connectivity of k -connected graphs

Stephen J. Kirkland, Israel Rocha, Vilmar Trevisan (2015)

Czechoslovak Mathematical Journal

Similarity:

Let G be a k -connected graph with k 2 . A hinge is a subset of k vertices whose deletion from G yields a disconnected graph. We consider the algebraic connectivity and Fiedler vectors of such graphs, paying special attention to the signs of the entries in Fiedler vectors corresponding to vertices in a hinge, and to vertices in the connected components at a hinge. The results extend those in Fiedler’s papers Algebraic connectivity of graphs (1973), A property of eigenvectors of nonnegative...

On the order of certain close to regular graphs without a matching of given size

Sabine Klinkenberg, Lutz Volkmann (2007)

Czechoslovak Mathematical Journal

Similarity:

A graph G is a { d , d + k } -graph, if one vertex has degree d + k and the remaining vertices of G have degree d . In the special case of k = 0 , the graph G is d -regular. Let k , p 0 and d , n 1 be integers such that n and p are of the same parity. If G is a connected { d , d + k } -graph of order n without a matching M of size 2 | M | = n - p , then we show in this paper the following: If d = 2 , then k 2 ( p + 2 ) and (i) n k + p + 6 . If d 3 is odd and t an integer with 1 t p + 2 , then (ii) n d + k + 1 for k d ( p + 2 ) , (iii) n d ( p + 3 ) + 2 t + 1 for d ( p + 2 - t ) + t k d ( p + 3 - t ) + t - 3 , (iv) n d ( p + 3 ) + 2 p + 7 for k p . If d 4 is even, then (v) n d + k + 2 - η for k d ( p + 3 ) + p + 4 + η , (vi) n d + k + p + 2 - 2 t = d ( p + 4 ) + p + 6 for k = d ( p + 3 ) + 4 + 2 t and p 1 ,...