A note on domination parameters of the conjunction of two special graphs

Maciej Zwierzchowski

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

Displaying similar documents to “A note on domination parameters of the conjunction of two special graphs”

Total domination of Cartesian products of graphs

Xinmin Hou (2007)

Discussiones Mathematicae Graph Theory

Similarity:

Let γₜ(G) and $γ_{p r} (G)$ denote the total domination and the paired domination numbers of graph G, respectively, and let G □ H denote the Cartesian product of graphs G and H. In this paper, we show that γₜ(G)γₜ(H) ≤ 5γₜ(G □ H), which improves the known result γₜ(G)γₜ(H) ≤ 6γₜ(G □ H) given by Henning and Rall.

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 $γ_{r}^{t} (G)$ , 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...

Graph domination in distance two

Gábor Bacsó, Attila Tálos, Zsolt Tuza (2005)

Discussiones Mathematicae Graph Theory

Similarity:

Let G = (V,E) be a graph, and k ≥ 1 an integer. A subgraph D is said to be k-dominating in G if every vertex of G-D is at distance at most k from some vertex of D. For a given class of graphs, Domₖ is the set of those graphs G in which every connected induced subgraph H has some k-dominating induced subgraph D ∈ which is also connected. In our notation, Dom coincides with Dom₁. In this paper we prove that $D o m D o m_{u} = D o m ₂_{u}$ holds for $_{u}$ = all connected graphs without induced $P_{u}$ (u ≥ 2). (In particular,...

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 $γ_{\times 2} (G)$ . If G ≠ C₅ is a connected graph of order n with minimum degree at least 2, then we show that $γ_{\times 2} (G) \leq 3 n / 4$ and we characterize those graphs achieving equality.

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.

Total domination versus paired domination

Oliver Schaudt (2012)

Discussiones Mathematicae Graph Theory

Similarity:

A dominating set of a graph G is a vertex subset that any vertex of G either belongs to or is adjacent to. A total dominating set is a dominating set whose induced subgraph does not contain isolated vertices. The minimal size of a total dominating set, the total domination number, is denoted by γₜ. The maximal size of an inclusionwise minimal total dominating set, the upper total domination number, is denoted by Γₜ. A paired dominating set is a dominating set whose induced subgraph has...

Power Domination in Knödel Graphs and Hanoi Graphs

Seethu Varghese, A. Vijayakumar, Andreas M. Hinz (2018)

Discussiones Mathematicae Graph Theory

Similarity:

In this paper, we study the power domination problem in Knödel graphs WΔ,2ν and Hanoi graphs [...] Hpn $H_{p}^{n}$ . We determine the power domination number of W3,2ν and provide an upper bound for the power domination number of Wr+1,2r+1 for r ≥ 3. We also compute the k-power domination number and the k-propagation radius of [...] Hp2 $H_{p}^{2}$ .

Edge-connectivity of strong products of graphs

Bostjan Bresar, Simon Spacapan (2007)

Discussiones Mathematicae Graph Theory

Similarity:

The strong product G₁ ⊠ G₂ of graphs G₁ and G₂ is the graph with V(G₁)×V(G₂) as the vertex set, and two distinct vertices (x₁,x₂) and (y₁,y₂) are adjacent whenever for each i ∈ 1,2 either $x_{i} = y_{i}$ or $x_{i} y_{i} \in E (G_{i})$ . In this note we show that for two connected graphs G₁ and G₂ the edge-connectivity λ (G₁ ⊠ G₂) equals minδ(G₁ ⊠ G₂), λ(G₁)(|V(G₂)| + 2|E(G₂)|), λ(G₂)(|V(G₁)| + 2|E(G₁)|). In addition, we fully describe the structure of possible minimum edge cut sets in strong products of graphs.

Eccentric distance sum index for some classes of connected graphs

Halina Bielak, Katarzyna Broniszewska (2017)

Annales Universitatis Mariae Curie-Sklodowska, sectio A – Mathematica

Similarity:

In this paper we show some properties of the eccentric distance sum index which is defined as follows $ξ^{d} (G) = \sum_{v \in V (G)} D (v) ε (v)$ . This index is widely used by chemists and biologists in their researches. We present a lower bound of this index for a new class of graphs.

A remark on the (2,2)-domination number

Torsten Korneffel, Dirk Meierling, Lutz Volkmann (2008)

Discussiones Mathematicae Graph Theory

Similarity:

A subset D of the vertex set of a graph G is a (k,p)-dominating set if every vertex v ∈ V(G)∖D is within distance k to at least p vertices in D. The parameter $γ_{k, p} (G)$ denotes the minimum cardinality of a (k,p)-dominating set of G. In 1994, Bean, Henning and Swart posed the conjecture that $γ_{k, p} (G) \leq (p / (p + k)) n (G)$ for any graph G with δₖ(G) ≥ k+p-1, where the latter means that every vertex is within distance k to at least k+p-1 vertices other than itself. In 2005, Fischermann and Volkmann confirmed this conjecture...

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

The hull number of strong product graphs

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

Discussiones Mathematicae Graph Theory

Similarity:

For a connected graph G with at least two vertices and S a subset of vertices, the convex hull ${[S]}_{G}$ is the smallest convex set containing S. The hull number h(G) is the minimum cardinality among the subsets S of V(G) with ${[S]}_{G} = V (G)$ . Upper bound for the hull number of strong product G ⊠ H of two graphs G and H is obtainted. Improved upper bounds are obtained for some class of strong product graphs. Exact values for the hull number of some special classes of strong product graphs are obtained. Graphs...

Radio numbers for generalized prism graphs

Paul Martinez, Juan Ortiz, Maggy Tomova, Cindy Wyels (2011)

Discussiones Mathematicae Graph Theory

Similarity:

A radio labeling is an assignment c:V(G) → N such that every distinct pair of vertices u,v satisfies the inequality d(u,v) + |c(u)-c(v)| ≥ diam(G) + 1. The span of a radio labeling is the maximum value. The radio number of G, rn(G), is the minimum span over all radio labelings of G. Generalized prism graphs, denoted $Z_{n, s}$ , s ≥ 1, n ≥ s, have vertex set (i,j) | i = 1,2 and j = 1,...,n and edge set ((i,j),(i,j ±1)) ∪ ((1,i),(2,i+σ)) | σ = -⌊(s-1)/2⌋...,0,...,⌊s/2⌋. In this paper we determine...

Restrained domination in unicyclic graphs

Johannes H. Hattingh, Ernst J. Joubert, Marc Loizeaux, Andrew R. Plummer, Lucas van der Merwe (2009)

Discussiones Mathematicae Graph Theory

Similarity:

Let G = (V,E) be a graph. A set S ⊆ V is a restrained dominating set if every vertex in V-S is adjacent to a vertex in S and to a vertex in V-S. The restrained domination number of G, denoted by $γ_{r} (G)$ , is the minimum cardinality of a restrained dominating set of G. A unicyclic graph is a connected graph that contains precisely one cycle. We show that if U is a unicyclic graph of order n, then $γ_{r} (U) \geq ⎡ n / 3 ⎤$ , and provide a characterization of graphs achieving this bound.

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

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

The order of uniquely partitionable graphs

Izak Broere, Marietjie Frick, Peter Mihók (1997)

Discussiones Mathematicae Graph Theory

Similarity:

Let ₁,...,ₙ be properties of graphs. A (₁,...,ₙ)-partition of a graph G is a partition V₁,...,Vₙ of V(G) such that, for each i = 1,...,n, the subgraph of G induced by $V_{i}$ has property $_{i}$ . If a graph G has a unique (₁,...,ₙ)-partition we say it is uniquely (₁,...,ₙ)-partitionable. We establish best lower bounds for the order of uniquely (₁,...,ₙ)-partitionable graphs, for various choices of ₁,...,ₙ.

Connected global offensive k-alliances in graphs

Lutz Volkmann (2011)

Discussiones Mathematicae Graph Theory

Similarity:

We consider finite graphs G with vertex set V(G). For a subset S ⊆ V(G), we define by G[S] the subgraph induced by S. By n(G) = |V(G) | and δ(G) we denote the order and the minimum degree of G, respectively. Let k be a positive integer. A subset S ⊆ V(G) is a connected global offensive k-alliance of the connected graph G, if G[S] is connected and |N(v) ∩ S | ≥ |N(v) -S | + k for every vertex v ∈ V(G) -S, where N(v) is the neighborhood of v. The connected global offensive k-alliance number...

Signed total domination number of a graph

Bohdan Zelinka (2001)

Czechoslovak Mathematical Journal

Similarity:

The signed total domination number of a graph is a certain variant of the domination number. If $v$ is a vertex of a graph $G$ , then $N (v)$ is its oper neighbourhood, i.e. the set of all vertices adjacent to $v$ in $G$ . A mapping $f : V (G) \to {- 1, 1}$ , where $V (G)$ is the vertex set of $G$ , is called a signed total dominating function (STDF) on $G$ , if $\sum_{x \in N (v)} f (x) \geq 1$ for each $v \in V (G)$ . The minimum of values $\sum_{x \in V (G)} f (x)$ , taken over all STDF’s of $G$ , is called the signed total domination number of $G$ and denoted by $γ_{s t} (G)$ . A theorem stating lower bounds for $γ_{s t} (G)$ is...

Wiener index of graphs with fixed number of pendant or cut-vertices

Dinesh Pandey, Kamal Lochan Patra (2022)

Czechoslovak Mathematical Journal

Similarity:

The Wiener index of a connected graph is defined as the sum of the distances between all unordered pairs of its vertices. We characterize the graphs which extremize the Wiener index among all graphs on $n$ vertices with $k$ pendant vertices. We also characterize the graph which minimizes the Wiener index over the graphs on $n$ vertices with $s$ cut-vertices.