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

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

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

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

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

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

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

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

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

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

Displaying similar documents to “Domination Parameters of a Graph and its Complement”

Various Bounds for Liar’s Domination Number

Abdollah Alimadadi, Doost Ali Mojdeh, Nader Jafari Rad (2016)

Discussiones Mathematicae Graph Theory

Similarity:

Let G = (V,E) be a graph. A set S ⊆ V is a dominating set if Uv∈S N[v] = V , where N[v] is the closed neighborhood of v. Let L ⊆ V be a dominating set, and let v be a designated vertex in V (an intruder vertex). Each vertex in L ∩ N[v] can report that v is the location of the intruder, but (at most) one x ∈ L ∩ N[v] can report any w ∈ N[x] as the intruder location or x can indicate that there is no intruder in N[x]. A dominating set L is called a liar’s dominating set if every v ∈ V...

Efficient (j,k)-domination

Robert R. Rubalcaba, Peter J. Slater (2007)

Discussiones Mathematicae Graph Theory

Similarity:

A dominating set S of a graph G is called efficient if |N[v]∩ S| = 1 for every vertex v ∈ V(G). That is, a dominating set S is efficient if and only if every vertex is dominated exactly once. In this paper, we investigate efficient multiple domination. There are several types of multiple domination defined in the literature: k-tuple domination, {k}-domination, and k-domination. We investigate efficient versions of the first two as well as a new type of multiple domination.

Hereditary domination and independence parameters

Wayne Goddard, Teresa Haynes, Debra Knisley (2004)

Discussiones Mathematicae Graph Theory

Similarity:

For a graphical property P and a graph G, we say that a subset S of the vertices of G is a P-set if the subgraph induced by S has the property P. Then the P-domination number of G is the minimum cardinality of a dominating P-set and the P-independence number the maximum cardinality of a P-set. We show that several properties of domination, independent domination and acyclic domination hold for arbitrary properties P that are closed under disjoint unions and subgraphs.

A Gallai-type equality for the total domination number of a graph

Sanming Zhou (2004)

Discussiones Mathematicae Graph Theory

Similarity:

We prove the following Gallai-type equality γₜ(G) + εₜ(G) = p for any graph G with no isolated vertex, where p is the number of vertices of G, γₜ(G) is the total domination number of G, and εₜ(G) is the maximum integer s such that there exists a spanning forest F with s the number of pendant edges of F minus the number of star components of F.

On the Totalk-Domination in Graphs

Sergio Bermudo, Juan C. Hernández-Gómez, José M. Sigarreta (2018)

Discussiones Mathematicae Graph Theory

Similarity:

Let G = (V, E) be a graph; a set S ⊆ V is a total k-dominating set if every vertex v ∈ V has at least k neighbors in S. The total k-domination number γkt(G) is the minimum cardinality among all total k-dominating sets. In this paper we obtain several tight bounds for the total k-domination number of a graph. In particular, we investigate the relationship between the total k-domination number of a graph and the order, the size, the girth, the minimum and maximum degree, the diameter,...

Partitioning a graph into a dominating set, a total dominating set, and something else

Michael A. Henning, Christian Löwenstein, Dieter Rautenbach (2010)

Discussiones Mathematicae Graph Theory

Similarity:

A recent result of Henning and Southey (A note on graphs with disjoint dominating and total dominating set, Ars Comb. 89 (2008), 159-162) implies that every connected graph of minimum degree at least three has a dominating set D and a total dominating set T which are disjoint. We show that the Petersen graph is the only such graph for which D∪T necessarily contains all vertices of the graph.

Total domination subdivision numbers of graphs

Teresa W. Haynes, Michael A. Henning, Lora S. Hopkins (2004)

Discussiones Mathematicae Graph Theory

Similarity:

A set S of vertices in a graph G = (V,E) is a total dominating set of G if every vertex of V is adjacent to a vertex in S. The total domination number of G is the minimum cardinality of a total dominating set of G. The total domination subdivision number of G is the minimum number of edges that must be subdivided (where each edge in G can be subdivided at most once) in order to increase the total domination number. First we establish bounds on the total domination subdivision number...

The bondage number of graphs: good and bad vertices

Vladimir Samodivkin (2008)

Discussiones Mathematicae Graph Theory

Similarity:

The domination number γ(G) of a graph G is the minimum number of vertices in a set D such that every vertex of the graph is either in D or is adjacent to a member of D. Any dominating set D of a graph G with |D| = γ(G) is called a γ-set of G. A vertex x of a graph G is called: (i) γ-good if x belongs to some γ-set and (ii) γ-bad if x belongs to no γ-set. The bondage number b(G) of a nonempty graph G is the cardinality of a smallest set of edges whose removal from G results in a graph...

The vertex monophonic number of a graph

A.P. Santhakumaran, P. Titus (2012)

Discussiones Mathematicae Graph Theory

Similarity:

For a connected graph G of order p ≥ 2 and a vertex x of G, a set S ⊆ V(G) is an x-monophonic set of G if each vertex v ∈ V(G) lies on an x -y monophonic path for some element y in S. The minimum cardinality of an x-monophonic set of G is defined as the x-monophonic number of G, denoted by mₓ(G). An x-monophonic set of cardinality mₓ(G) is called a mₓ-set of G. We determine bounds for it and characterize graphs which realize these bounds. A connected graph of order p with vertex monophonic...

Vertices Contained In All Or In No Minimum Semitotal Dominating Set Of A Tree

Michael A. Henning, Alister J. Marcon (2016)

Discussiones Mathematicae Graph Theory

Similarity:

Let G be a graph with no isolated vertex. In this paper, we study a parameter that is squeezed between arguably the two most important domination parameters; namely, the domination number, γ(G), and the total domination number, γt(G). A set S of vertices in a graph G is a semitotal dominating set of G if it is a dominating set of G and every vertex in S is within distance 2 of another vertex of S. The semitotal domination number, γt2(G), is the minimum cardinality of a semitotal dominating...

The Distance Roman Domination Numbers of Graphs

Hamideh Aram, Sepideh Norouzian, Seyed Mahmoud Sheikholeslami (2013)

Discussiones Mathematicae Graph Theory

Similarity:

Let k be a positive integer, and let G be a simple graph with vertex set V (G). A k-distance Roman dominating function on G is a labeling f : V (G) → {0, 1, 2} such that for every vertex with label 0, there is a vertex with label 2 at distance at most k from each other. The weight of a k-distance Roman dominating function f is the value w(f) =∑v∈V f(v). The k-distance Roman domination number of a graph G, denoted by γkR (D), equals the minimum weight of a k-distance Roman dominating...