Displaying similar documents to “Various Bounds for Liar’s Domination Number”

Domination Parameters of a Graph and its Complement

Wyatt J. Desormeaux, Teresa W. Haynes, Michael A. Henning (2018)

Discussiones Mathematicae Graph Theory

Similarity:

A dominating set in a graph G is a set S of vertices such that every vertex in V (G) S is adjacent to at least one vertex in S, and the domination number of G is the minimum cardinality of a dominating set of G. Placing constraints on a dominating set yields different domination parameters, including total, connected, restrained, and clique domination numbers. In this paper, we study relationships among domination parameters of a graph and its complement.

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

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.

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.

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

Lower bounds for the domination number

Ermelinda Delaviña, Ryan Pepper, Bill Waller (2010)

Discussiones Mathematicae Graph Theory

Similarity:

In this note, we prove several lower bounds on the domination number of simple connected graphs. Among these are the following: the domination number is at least two-thirds of the radius of the graph, three times the domination number is at least two more than the number of cut-vertices in the graph, and the domination number of a tree is at least as large as the minimum order of a maximal matching.

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

Cubic Graphs with Total Domatic Number at Least Two

Saieed Akbari, Mohammad Motiei, Sahand Mozaffari, Sina Yazdanbod (2018)

Discussiones Mathematicae Graph Theory

Similarity:

Let G be a graph with no isolated vertex. A total dominating set of G is a set S of vertices of G such that every vertex is adjacent to at least one vertex in S. The total domatic number of a graph is the maximum number of total dominating sets which partition the vertex set of G. In this paper we provide a criterion under which a cubic graph has total domatic number at least two.

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.

A Note on Non-Dominating Set Partitions in Graphs

Wyatt J. Desormeaux, Teresa W. Haynes, Michael A. Henning (2016)

Discussiones Mathematicae Graph Theory

Similarity:

A set S of vertices of a graph G is a dominating set if every vertex not in S is adjacent to a vertex of S and is a total dominating set if every vertex of G is adjacent to a vertex of S. The cardinality of a minimum dominating (total dominating) set of G is called the domination (total domination) number. A set that does not dominate (totally dominate) G is called a non-dominating (non-total dominating) set of G. A partition of the vertices of G into non-dominating (non-total dominating)...

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