Domination in Analysis
Denny Gulick (1973)
Publications du Département de mathématiques (Lyon)
Similarity:
Displaying similar documents to “Note on the split domination number of the Cartesian product of paths”
Domination in Analysis
A Note on the Locating-Total Domination in Graphs
Mirka Miller, R. Sundara Rajan, R. Jayagopal, Indra Rajasingh, Paul Manuel (2017)
Discussiones Mathematicae Graph Theory
Similarity:
In this paper we obtain a sharp (improved) lower bound on the locating-total domination number of a graph, and show that the decision problem for the locating-total domination is NP-complete.
Graphs with equal domination and 2-distance domination numbers
Joanna Raczek (2011)
Discussiones Mathematicae Graph Theory
Similarity:
Let G = (V,E) be a graph. The distance between two vertices u and v in a connected graph G is the length of the shortest (u-v) path in G. A set D ⊆ V(G) is a dominating set if every vertex of G is at distance at most 1 from an element of D. The domination number of G is the minimum cardinality of a dominating set of G. A set D ⊆ V(G) is a 2-distance dominating set if every vertex of G is at distance at most 2 from an element of D. The 2-distance domination number of G is the minimum...
On the Complexity of Reinforcement in Graphs
Nader Jafari Rad (2016)
Discussiones Mathematicae Graph Theory
Similarity:
We show that the decision problem for p-reinforcement, p-total rein- forcement, total restrained reinforcement, and k-rainbow reinforcement are NP-hard for bipartite graphs.
A note on domination parameters of the conjunction of two special graphs
Maciej Zwierzchowski (2001)
Discussiones Mathematicae Graph Theory
Similarity:
A dominating set D of G is called a split dominating set of G if the subgraph induced by the subset V(G)-D is disconnected. The cardinality of a minimum split dominating set is called the minimum split domination number of G. Such subset and such number was introduced in [4]. In [2], [3] the authors estimated the domination number of products of graphs. More precisely, they were study products of paths. Inspired by those results we give another estimation of the domination number of...
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...
Generalized domination, independence and irredudance in graphs
Mieczysław Borowiecki, Danuta Michalak, Elżbieta Sidorowicz (1997)
Discussiones Mathematicae Graph Theory
Similarity:
The purpose of this paper is to present some basic properties of 𝓟-dominating, 𝓟-independent, and 𝓟-irredundant sets in graphs which generalize well-known properties of dominating, independent and irredundant sets, respectively.
On The Roman Domination Stable Graphs
Majid Hajian, Nader Jafari Rad (2017)
Discussiones Mathematicae Graph Theory
Similarity:
A Roman dominating function (or just RDF) on a graph G = (V,E) is a function f : V → {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 an RDF f is the value f(V (G)) = Pu2V (G) f(u). The Roman domination number of a graph G, denoted by R(G), is the minimum weight of a Roman dominating function on G. A graph G is Roman domination stable if the Roman domination number of G remains unchanged under...
Paired-domination
S. Fitzpatrick, B. Hartnell (1998)
Discussiones Mathematicae Graph Theory
Similarity:
We are interested in dominating sets (of vertices) with the additional property that the vertices in the dominating set can be paired or matched via existing edges in the graph. This could model the situation of guards or police where each has a partner or backup. This paper will focus on those graphs in which the number of matched pairs of a minimum dominating set of this type equals the size of some maximal matching in the graph. In particular, we characterize the leafless graphs of...
Improving some bounds for dominating Cartesian products
Bert L. Hartnell, Douglas F. Rall (2003)
Discussiones Mathematicae Graph Theory
Similarity:
The study of domination in Cartesian products has received its main motivation from attempts to settle a conjecture made by V.G. Vizing in 1968. He conjectured that γ(G)γ(H) is a lower bound for the domination number of the Cartesian product of any two graphs G and H. Most of the progress on settling this conjecture has been limited to verifying the conjectured lower bound if one of the graphs has a certain structural property. In addition, a number of authors have established bounds...
Some results on total domination in direct products of graphs
Paul Dorbec, Sylvain Gravier, Sandi Klavžar, Simon Spacapan (2006)
Discussiones Mathematicae Graph Theory
Similarity:
Upper and lower bounds on the total domination number of the direct product of graphs are given. The bounds involve the {2}-total domination number, the total 2-tuple domination number, and the open packing number of the factors. Using these relationships one exact total domination number is obtained. An infinite family of graphs is constructed showing that the bounds are best possible. The domination number of direct products of graphs is also bounded from below.
On the total restrained domination number of direct products of graphs
Wai Chee Shiu, Hong-Yu Chen, Xue-Gang Chen, Pak Kiu Sun (2012)
Discussiones Mathematicae Graph Theory
Similarity:
Let G = (V,E) be a graph. A total restrained dominating set is a set S ⊆ V where every vertex in V∖S is adjacent to a vertex in S as well as to another vertex in V∖S, and every vertex in S is adjacent to another vertex in S. The total restrained domination number of G, denoted by , is the smallest cardinality of a total restrained dominating set of G. We determine lower and upper bounds on the total restrained domination number of the direct product of two graphs. Also, we show that...
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 note on domination in bipartite graphs
Tobias Gerlach, Jochen Harant (2002)
Discussiones Mathematicae Graph Theory
Similarity:
DOMINATING SET remains NP-complete even when instances are restricted to bipartite graphs, however, in this case VERTEX COVER is solvable in polynomial time. Consequences to VECTOR DOMINATING SET as a generalization of both are discussed.
Upper Bounds on the Signed Total (K, K)-Domatic Number of Graphs
Lutz Volkmann (2015)
Discussiones Mathematicae Graph Theory
Similarity:
Let G be a graph with vertex set V (G), and let f : V (G) → {−1, 1} be a two-valued function. If k ≥ 1 is an integer and Σx∈N(v) f(x) ≥ k for each v ∈ V (G), where N(v) is the neighborhood of v, then f is a signed total k-dominating function on G. A set {f1, f2, . . . , fd} of distinct signed total k-dominating functions on G with the property that Σdi=1 fi(x) ≤ k for each x ∈ V (G), is called a signed total (k, k)-dominating family (of functions) on G. The maximum number of functions...
A Note on Path Domination
Liliana Alcón (2016)
Discussiones Mathematicae Graph Theory
Similarity:
We study domination between different types of walks connecting two non-adjacent vertices u and v of a graph (shortest paths, induced paths, paths, tolled walks). We succeeded in characterizing those graphs in which every uv-walk of one particular kind dominates every uv-walk of other specific kind. We thereby obtained new characterizations of standard graph classes like chordal, interval and superfragile graphs.
Domination and leaf density in graphs
Anders Sune Pedersen (2005)
Discussiones Mathematicae Graph Theory
Similarity:
The domination number γ(G) of a graph G is the minimum cardinality of a subset D of V(G) with the property that each vertex of V(G)-D is adjacent to at least one vertex of D. For a graph G with n vertices we define ε(G) to be the number of leaves in G minus the number of stems in G, and we define the leaf density ζ(G) to equal ε(G)/n. We prove that for any graph G with no isolated vertex, γ(G) ≤ n(1- ζ(G))/2 and we characterize the extremal graphs for this bound. Similar results are...
Twin Minus Total Domination Numbers In Directed Graphs
Nasrin Dehgardi, Maryam Atapour (2017)
Discussiones Mathematicae Graph Theory
Similarity:
Let D = (V,A) be a finite simple directed graph (shortly, digraph). A function f : V → {−1, 0, 1} is called a twin minus total dominating function (TMTDF) if f(N−(v)) ≥ 1 and f(N+(v)) ≥ 1 for each vertex v ∈ V. The twin minus total domination number of D is y*mt(D) = min{w(f) | f is a TMTDF of D}. In this paper, we initiate the study of twin minus total domination numbers in digraphs and we present some lower bounds for y*mt(D) in terms of the order, size and maximum and minimum in-degrees...
The Domination Number of K 3 n
John Georges, Jianwei Lin, David Mauro (2014)
Discussiones Mathematicae Graph Theory
Similarity:
Let K3n denote the Cartesian product Kn□Kn□Kn, where Kn is the complete graph on n vertices. We show that the domination number of K3n is [...]
Eternal Domination: Criticality and Reachability
William F. Klostermeyer, Gary MacGillivray (2017)
Discussiones Mathematicae Graph Theory
Similarity:
We show that for every minimum eternal dominating set, D, of a graph G and every vertex v ∈ D, there is a sequence of attacks at the vertices of G which can be defended in such a way that an eternal dominating set not containing v is reached. The study of the stronger assertion that such a set can be reached after a single attack is defended leads to the study of graphs which are critical in the sense that deleting any vertex reduces the eternal domination number. Examples of these graphs...
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,...