On the total restrained domination number of direct products of graphs

Wai Chee Shiu; Hong-Yu Chen; Xue-Gang Chen; Pak Kiu Sun

Displaying similar documents to “On the total restrained domination number of direct products of graphs”

Bounding the Openk-Monopoly Number of Strong Product Graphs

Dorota Kuziak, Iztok Peterin, Ismael G. Yero (2018)

Discussiones Mathematicae Graph Theory

Similarity:

Let G = (V, E) be a simple graph without isolated vertices and minimum degree δ, and let k ∈ 1 − ⌈δ/2⌉, . . . , ⌊δ/2⌋ be an integer. Given a set M ⊂ V, a vertex v of G is said to be k-controlled by M if [...] δM(v)≥δG(v)2+k $δ_{M} (v) \geq \frac{δ_{G} (v)}{2} + k$ , where δM(v) represents the number of neighbors of v in M and δG(v) the degree of v in G. A set M is called an open k-monopoly if every vertex v of G is k-controlled by M. The minimum cardinality of any open k-monopoly is the open k-monopoly number of G. In this...

On total restrained domination in graphs

De-xiang Ma, Xue-Gang Chen, Liang Sun (2005)

Czechoslovak Mathematical Journal

Similarity:

In this paper we initiate the study of total restrained domination in graphs. Let $G = (V, E)$ be a graph. A total restrained dominating set is a set $S \subseteq 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 $γ_{r}^{t} (G)$ , is the smallest cardinality of a total restrained dominating set of $G$ . First, some exact values and sharp bounds for $γ_{r}^{t} (G)$ are given in Section 2....

On well-covered graphs of odd girth 7 or greater

Bert Randerath, Preben Dahl Vestergaard (2002)

Discussiones Mathematicae Graph Theory

Similarity:

A maximum independent set of vertices in a graph is a set of pairwise nonadjacent vertices of largest cardinality α. Plummer [14] defined a graph to be well-covered, if every independent set is contained in a maximum independent set of G. One of the most challenging problems in this area, posed in the survey of Plummer [15], is to find a good characterization of well-covered graphs of girth 4. We examine several subclasses of well-covered graphs of girth ≥ 4 with respect to the odd girth...

Independent transversal domination in graphs

Ismail Sahul Hamid (2012)

Discussiones Mathematicae Graph Theory

Similarity:

A set S ⊆ V of vertices in a graph G = (V, E) is called a dominating set if every vertex in V-S is adjacent to a vertex in S. A dominating set which intersects every maximum independent set in G is called an independent transversal dominating set. The minimum cardinality of an independent transversal dominating set is called the independent transversal domination number of G and is denoted by $γ_{i t} (G)$ . In this paper we begin an investigation of this parameter.

Minus total domination in graphs

Hua Ming Xing, Hai-Long Liu (2009)

Czechoslovak Mathematical Journal

Similarity:

A three-valued function $f V \to {- 1, 0, 1}$ defined on the vertices of a graph $G = (V, E)$ is a minus total dominating function (MTDF) if the sum of its function values over any open neighborhood is at least one. That is, for every $v \in V$ , $f (N (v)) \geq 1$ , where $N (v)$ consists of every vertex adjacent to $v$ . The weight of an MTDF is $f (V) = \sum f (v)$ , over all vertices $v \in V$ . The minus total domination number of a graph $G$ , denoted $γ_{t}^{-} (G)$ , equals the minimum weight of an MTDF of $G$ . In this paper, we discuss some properties of minus total domination on a graph...

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 \geq 1$ be an integer. A subset $D \subseteq V (G)$ is called a if every vertex $v \in 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) \geq k + 1$ , then we prove that $γ_{k + 1} (G) \leq \frac{| V (G) | + γ_{k} (G)}{2} .$ In addition, we present a characterization of a special class of graphs attaining equality in this inequality.

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

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

Matchings and total domination subdivision number in graphs with few induced 4-cycles

Odile Favaron, Hossein Karami, Rana Khoeilar, Seyed Mahmoud Sheikholeslami (2010)

Discussiones Mathematicae Graph Theory

Similarity:

A set S of vertices of a graph G = (V,E) without isolated vertex is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. The total domination number γₜ(G) is the minimum cardinality of a total dominating set of G. The total 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 total domination number. Favaron, Karami, Khoeilar and Sheikholeslami (Journal...

On domination number of 4-regular graphs

Hailong Liu, Liang Sun (2004)

Czechoslovak Mathematical Journal

Similarity:

Let $G$ be a simple graph. A subset $S \subseteq V$ is a dominating set of $G$ , if for any vertex $v \in V - S$ there exists a vertex $u \in S$ such that $u v \in E (G)$ . The domination number, denoted by $γ (G)$ , is the minimum cardinality of a dominating set. In this paper we prove that if $G$ is a 4-regular graph with order $n$ , then $γ (G) \leq \frac{4}{11} n$ .

Vertex-disjoint stars in graphs

Katsuhiro Ota (2001)

Discussiones Mathematicae Graph Theory

Similarity:

In this paper, we give a sufficient condition for a graph to contain vertex-disjoint stars of a given size. It is proved that if the minimum degree of the graph is at least k+t-1 and the order is at least (t+1)k + O(t²), then the graph contains k vertex-disjoint copies of a star $K_{1, t}$ . The condition on the minimum degree is sharp, and there is an example showing that the term O(t²) for the number of uncovered vertices is necessary in a sense.

A characterization of roman trees

Michael A. Henning (2002)

Discussiones Mathematicae Graph Theory

Similarity:

A Roman dominating function (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 f is $w (f) = \sum_{v \in V} f (v)$ . The Roman domination number is the minimum weight of an RDF in G. It is known that for every graph G, the Roman domination number of G is bounded above by twice its domination number. Graphs which have Roman domination number equal to twice their domination number...