Pełnotekstowe zasoby PLDML oraz innych baz dziedzinowych są już dostępne w nowej Bibliotece Nauki.
Zapraszamy na https://bibliotekanauki.pl
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 24

Liczba wyników na stronie
first rewind previous Strona / 2 next fast forward last

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych:  domination number
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 2 next fast forward last
1
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Lower bound on the domination number of a tree

100%
Lemańska M.
Discussiones Mathematicae Graph Theory
|
2004
|
tom 24
|
nr 2
165-169
EN
>We prove that the domination number γ(T) of a tree T on n ≥ 3 vertices and with n₁ endvertices satisfies inequality γ(T) ≥ (n+2-n₁)/3 and we characterize the extremal graphs.
2
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Weak roman domination in graphs

100%
Roushini Leely Pushpam P., Malini Mai T.
Discussiones Mathematicae Graph Theory
|
2011
|
tom 31
|
nr 1
161-170
EN
Let G = (V,E) be a graph and f be a function f:V → {0,1,2}. A vertex u with f(u) = 0 is said to be undefended with respect to f, if it is not adjacent to a vertex with positive weight. The function f is a weak Roman dominating function (WRDF) if each vertex u with f(u) = 0 is adjacent to a vertex v with f(v) > 0 such that the function f': V → {0,1,2} defined by f'(u) = 1, f'(v) = f(v)-1 and f'(w) = f(w) if w ∈ V-{u,v}, has no undefended vertex. The weight of f is $w(f) = ∑_{v ∈ V}f(v)$. The weak Roman domination number, denoted by $γ_r(G)$, is the minimum weight of a WRDF in G. In this paper, we characterize the class of trees and split graphs for which $γ_r(G) = γ(G)$ and find $γ_r$-value for a caterpillar, a 2×n grid graph and a complete binary tree.
3
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Total outer-connected domination in trees

100%
Cyman J.
Discussiones Mathematicae Graph Theory
|
2010
|
tom 30
|
nr 3
377-383
EN
Let G = (V,E) be a graph. Set D ⊆ V(G) is a total outer-connected dominating set of G if D is a total dominating set in G and G[V(G)-D] is connected. The total outer-connected domination number of G, denoted by $γ_{tc}(G)$, is the smallest cardinality of a total outer-connected dominating set of G. We show that if T is a tree of order n, then $γ_{tc}(T) ≥ ⎡2n/3⎤$. Moreover, we constructively characterize the family of extremal trees T of order n achieving this lower bound.
4
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Improving some bounds for dominating Cartesian products

80%
Hartnell B., Rall D.
Discussiones Mathematicae Graph Theory
|
2003
|
tom 23
|
nr 2
261-272
EN
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 for dominating the Cartesian product of any two graphs. We show how it is possible to improve some of these bounds by imposing conditions on both graphs. For example, we establish a new lower bound for the domination number of T T, when T is a tree, and we improve an upper bound of Vizing in the case when one of the graphs has k > 1 dominating sets which cover the vertex set and the other has a dominating set which partitions in a certain way.
5
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Vizing's conjecture and the one-half argument

80%
Hartnell B., Rall D.
Discussiones Mathematicae Graph Theory
|
1995
|
tom 15
|
nr 2
205-216
EN
The domination number of a graph G is the smallest order, γ(G), of a dominating set for G. A conjecture of V. G. Vizing [5] states that for every pair of graphs G and H, γ(G☐H) ≥ γ(G)γ(H), where G☐H denotes the Cartesian product of G and H. We show that if the vertex set of G can be partitioned in a certain way then the above inequality holds for every graph H. The class of graphs G which have this type of partitioning includes those whose 2-packing number is no smaller than γ(G)-1 as well as the collection of graphs considered by Barcalkin and German in [1]. A crucial part of the proof depends on the well-known fact that the domination number of any connected graph of order at least two is no more than half its order.
6
Content available remote

On the Domination of Cartesian Product of Directed Cycles: Results for Certain Equivalence Classes of Lengths

80%
Mollard M.
Discussiones Mathematicae Graph Theory
|
2013
|
tom 33
|
nr 2
387-394
EN
Let (−→ Cm2−→ Cn) be the domination number of the Cartesian product of directed cycles −→ Cm and −→ Cn for m, n ≥ 2. Shaheen [13] and Liu et al. ([11], [12]) determined the value of (−→ Cm2−→ Cn) when m ≤ 6 and [12] when both m and n ≡ 0(mod 3). In this article we give, in general, the value of (−→ Cm2−→ Cn) when m ≡ 2(mod 3) and improve the known lower bounds for most of the remaining cases. We also disprove the conjectured formula for the case m ≡ 0(mod 3) appearing in [12].
7
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Effect of edge-subdivision on vertex-domination in a graph

80%
Bhattacharya A., Vijayakumar G.
Discussiones Mathematicae Graph Theory
|
2002
|
tom 22
|
nr 2
335-347
EN
Let G be a graph with Δ(G) > 1. It can be shown that the domination number of the graph obtained from G by subdividing every edge exactly once is more than that of G. So, let ξ(G) be the least number of edges such that subdividing each of these edges exactly once results in a graph whose domination number is more than that of G. The parameter ξ(G) is called the subdivision number of G. This notion has been introduced by S. Arumugam and S. Velammal. They have conjectured that for any graph G with Δ(G) > 1, ξ(G) ≤ 3. We show that the conjecture is false and construct for any positive integer n ≥ 3, a graph G of order n with ξ(G) > [1/3]log₂ n. The main results of this paper are the following: (i) For any connected graph G with at least three vertices, ξ(G) ≤ γ(G)+1 where γ(G) is the domination number of G. (ii) If G is a connected graph of sufficiently large order n, then ξ(G) ≤ 4√n ln n+5
8
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

The cobondage number of a graph

80%
Kulli V., Janakiram B.
Discussiones Mathematicae Graph Theory
|
1996
|
tom 16
|
nr 2
111-117
EN
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 b_c(G) for some standard graphs are found and some bounds are obtained. Also, a Nordhaus-Gaddum type result is established.
9
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On well-covered graphs of odd girth 7 or greater

80%
Randerath B., Vestergaard P.
Discussiones Mathematicae Graph Theory
|
2002
|
tom 22
|
nr 1
159-172
EN
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 of the graph. We prove that every isolate-vertex-free well-covered graph G containing neither C₃, C₅ nor C₇ as a subgraph is even very well-covered. Here, a isolate-vertex-free well-covered graph G is called very well-covered, if G satisfies α(G) = n/2. A vertex set D of G is dominating if every vertex not in D is adjacent to some vertex in D. The domination number γ(G) is the minimum order of a dominating set of G. Obviously, the inequality γ(G) ≤ α(G) holds. The family $𝓖_{γ=α}$ of graphs G with γ(G) = α(G) forms a subclass of well-covered graphs. We prove that every connected member G of $𝓖_{γ=α}$ containing neither C₃ nor C₅ as a subgraph is a K₁, C₄,C₇ or a corona graph.
10
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Domination in partitioned graphs

80%
Tuza Z., Vestergaard P.
Discussiones Mathematicae Graph Theory
|
2002
|
tom 22
|
nr 1
199-210
EN
Let V₁, V₂ be a partition of the vertex set in a graph G, and let $γ_i$ denote the least number of vertices needed in G to dominate $V_i$. We prove that γ₁+γ₂ ≤ [4/5]|V(G)| for any graph without isolated vertices or edges, and that equality occurs precisely if G consists of disjoint 5-paths and edges between their centers. We also give upper and lower bounds on γ₁+γ₂ for graphs with minimum valency δ, and conjecture that γ₁+γ₂ ≤ [4/(δ+3)]|V(G)| for δ ≤ 5. As δ gets large, however, the largest possible value of (γ₁+γ₂)/|V(G)| is shown to grow with the order of (logδ)/(δ).
11
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On Vizing's conjecture

80%
Bresar B.
Discussiones Mathematicae Graph Theory
|
2001
|
tom 21
|
nr 1
5-11
EN
A dominating set D for a graph G is a subset of V(G) such that any vertex in V(G)-D has a neighbor in D, and a domination number γ(G) is the size of a minimum dominating set for G. For the Cartesian product G ⃞ H Vizing's conjecture [10] states that γ(G ⃞ H) ≥ γ(G)γ(H) for every pair of graphs G,H. In this paper we introduce a new concept which extends the ordinary domination of graphs, and prove that the conjecture holds when γ(G) = γ(H) = 3.
12
Content available remote

The Domination Number of K3n

80%
Georges J., Lin J., Mauro D.
Discussiones Mathematicae Graph Theory
|
2014
|
tom 34
|
nr 3
629-632
EN
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 [...]
13
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Characterization of trees with equal 2-domination number and domination number plus two

80%
Chellali M., Volkmann L.
Discussiones Mathematicae Graph Theory
|
2011
|
tom 31
|
nr 4
687-697
EN
Let G = (V(G),E(G)) be a simple graph, and let k be a positive integer. A subset D of V(G) is a k-dominating set if every vertex of V(G) - D is dominated at least k times by D. The k-domination number γₖ(G) is the minimum cardinality of a k-dominating set of G. In [5] Volkmann showed that for every nontrivial tree T, γ₂(T) ≥ γ₁(T)+1 and characterized extremal trees attaining this bound. In this paper we characterize all trees T with γ₂(T) = γ₁(T)+2.
14
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Graphs with equal domination and 2-distance domination numbers

80%
Raczek J.
Discussiones Mathematicae Graph Theory
|
2011
|
tom 31
|
nr 2
375-385
EN
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 cardinality of a 2-distance dominating set of G. We characterize all trees and all unicyclic graphs with equal domination and 2-distance domination numbers.
15
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Lower bounds for the domination number

80%
Delaviña E., Pepper R., Waller B.
Discussiones Mathematicae Graph Theory
|
2010
|
tom 30
|
nr 3
475-487
EN
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.
16
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Note on the split domination number of the Cartesian product of paths

80%
Zwierzchowski M.
Discussiones Mathematicae Graph Theory
|
2005
|
tom 25
|
nr 1-2
79-84
EN
In this note the split domination number of the Cartesian product of two paths is considered. Our results are related to [2] where the domination number of Pₘ ☐ Pₙ was studied. The split domination number of P₂ ☐ Pₙ is calculated, and we give good estimates for the split domination number of Pₘ ☐ Pₙ expressed in terms of its domination number.
17
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Dominant-matching graphs

80%
Zverovich I., Zverovich O.
Discussiones Mathematicae Graph Theory
|
2004
|
tom 24
|
nr 3
485-490
EN
We introduce a new hereditary class of graphs, the dominant-matching graphs, and we characterize it in terms of forbidden induced subgraphs.
18
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

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

80%
Zhou S.
Discussiones Mathematicae Graph Theory
|
2004
|
tom 24
|
nr 3
539-543
EN
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.
19
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On the (2,2)-domination number of trees

80%
Lu Y., Hou X., Xu J.-M.
Discussiones Mathematicae Graph Theory
|
2010
|
tom 30
|
nr 2
185-199
EN
Let γ(G) and $γ_{2,2}(G)$ denote the domination number and (2,2)-domination number of a graph G, respectively. In this paper, for any nontrivial tree T, we show that $(2(γ(T)+1))/3 ≤ γ_{2,2}(T) ≤ 2γ(T)$. Moreover, we characterize all the trees achieving the equalities.
20
Content available remote

Domination Game Critical Graphs

71%
Bujtás C., Klavžar S., Košmrlj G.
Discussiones Mathematicae Graph Theory
|
2015
|
tom 35
|
nr 4
781-796
EN
The domination game is played on a graph G by two players who alternately take turns by choosing a vertex such that in each turn at least one previously undominated vertex is dominated. The game is over when each vertex becomes dominated. One of the players, namely Dominator, wants to finish the game as soon as possible, while the other one wants to delay the end. The number of turns when Dominator starts the game on G and both players play optimally is the graph invariant γg(G), named the game domination number. Here we study the γg-critical graphs which are critical with respect to vertex predomination. Besides proving some general properties, we characterize γg-critical graphs with γg = 2 and with γg = 3, moreover for each n we identify the (infinite) class of all γg-critical ones among the nth powers CnN of cycles. Along the way we determine γg(CnN) for all n and N. Results of a computer search for γg-critical trees are presented and several problems and research directions are also listed.
first rewind previous Strona / 2 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.