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: 14

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

Wyniki wyszukiwania

help Sortuj według:

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

On locating and differentiating-total domination in trees

100%
Chellali M.
Discussiones Mathematicae Graph Theory
|
2008
|
tom 28
|
nr 3
383-392
EN
A total dominating set of a graph G = (V,E) with no isolated vertex is a set S ⊆ V such that every vertex is adjacent to a vertex in S. A total dominating set S of a graph G is a locating-total dominating set if for every pair of distinct vertices u and v in V-S, N(u)∩S ≠ N(v)∩S, and S is a differentiating-total dominating set if for every pair of distinct vertices u and v in V, N[u]∩S ≠ N[v] ∩S. Let $γₜ^L(G)$ and $γₜ^D(G)$ be the minimum cardinality of a locating-total dominating set and a differentiating-total dominating set of G, respectively. We show that for a nontrivial tree T of order n, with l leaves and s support vertices, $γₜ^L(T) ≥ max{2(n+l-s+1)/5,(n+2-s)/2}$, and for a tree of order n ≥ 3, $γₜ^D(T) ≥ 3(n+l-s+1)/7$, improving the lower bounds of Haynes, Henning and Howard. Moreover we characterize the trees satisfying $γₜ^L(T) = 2(n+l- s+1)/5$ or $γₜ^D(T) = 3(n+l-s+1)/7$.
2
Content available remote

Strong Equality Between the Roman Domination and Independent Roman Domination Numbers in Trees

64%
Chellali M., Rad N. J.
Discussiones Mathematicae Graph Theory
|
2013
|
tom 33
|
nr 2
337-346
EN
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 an RDF is the value f(V (G)) = P u2V (G) f(u). An RDF f in a graph G is independent if no two vertices assigned positive values are adjacent. The Roman domination number R(G) (respectively, the independent Roman domination number iR(G)) is the minimum weight of an RDF (respectively, independent RDF) on G. We say that R(G) strongly equals iR(G), denoted by R(G) ≡ iR(G), if every RDF on G of minimum weight is independent. In this paper we provide a constructive characterization of trees T with R(T) ≡ iR(T).
3
Content available remote

Théorème de la clôture lq-modulaire et applications

64%
Chellali M., Fliouet E.
Colloquium Mathematicum
|
2011
|
tom 122
|
nr 2
275-287
EN
Let K be a purely inseparable extension of a field k of characteristic p ≠ 0. Suppose that $[k:k^{p}]$ is finite. We recall that K/k is lq-modular if K is modular over a finite extension of k. Moreover, there exists a smallest extension m/k (resp. M/K) such that K/m (resp. M/k) is lq-modular. Our main result states the existence of a greatest lq-modular and relatively perfect subextension of K/k. Other results can be summarized in the following: 1. The product of lq-modular extensions over k is lq-modular over k. 2. If we augment the ground field of an lq-modular extension, the lq-modularity is preserved. Generally, for all intermediate fields K₁ and K₂ of K/k such that K₁/k is lq-modular over k, K₁(K₂)/K₂ is lq-modular. By successive application of the theorem on lq-modular closure (our main result), we deduce that the smallest extension m/k of K/k such that K/m is lq-modular is non-trivial (i.e. m ≠ K). More precisely if K/k is infinite, then K/m is infinite.
4
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Global alliances and independence in trees

64%
Chellali M., Haynes T.
Discussiones Mathematicae Graph Theory
|
2007
|
tom 27
|
nr 1
19-27
EN
A global defensive (respectively, offensive) alliance in a graph G = (V,E) is a set of vertices S ⊆ V with the properties that every vertex in V-S has at least one neighbor in S, and for each vertex v in S (respectively, in V-S) at least half the vertices from the closed neighborhood of v are in S. These alliances are called strong if a strict majority of vertices from the closed neighborhood of v must be in S. For each kind of alliance, the associated parameter is the minimum cardinality of such an alliance. We determine relationships among these four parameters and the vertex independence number for trees.
5
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

64%
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.
6
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On the dominator colorings in trees

64%
Merouane H., Chellali M.
Discussiones Mathematicae Graph Theory
|
2012
|
tom 32
|
nr 4
677-683
EN
In a graph G, a vertex is said to dominate itself and all its neighbors. A dominating set of a graph G is a subset of vertices that dominates every vertex of G. The domination number γ(G) is the minimum cardinality of a dominating set of G. A proper coloring of a graph G is a function from the set of vertices of the graph to a set of colors such that any two adjacent vertices have different colors. A dominator coloring of a graph G is a proper coloring such that every vertex of V dominates all vertices of at least one color class (possibly its own class). The dominator chromatic number $χ_d(G)$ is the minimum number of color classes in a dominator coloring of G. Gera showed that every nontrivial tree T satisfies $γ(T)+1 ≤ χ_d(T) ≤ γ(T)+2$. In this note we characterize nontrivial trees T attaining each bound.
7
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Double domination critical and stable graphs upon vertex removal

64%
Khelifi S., Chellali M.
Discussiones Mathematicae Graph Theory
|
2012
|
tom 32
|
nr 4
643-657
EN
In a graph a vertex is said to dominate itself and all its neighbors. A double dominating set of a graph G is a subset of vertices that dominates every vertex of G at least twice. The double domination number of G, denoted $γ_{×2}(G)$, is the minimum cardinality among all double dominating sets of G. We consider the effects of vertex removal on the double domination number of a graph. A graph G is $γ_{×2}$-vertex critical graph ($γ_{×2}$-vertex stable graph, respectively) if the removal of any vertex different from a support vertex decreases (does not change, respectively) $γ_{×2}$(G). In this paper we investigate various properties of these graphs. Moreover, we characterize $γ_{×2}$-vertex critical trees and $γ_{×2}$-vertex stable trees.
8
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Trees with equal 2-domination and 2-independence numbers

64%
Chellali M., Meddah N.
Discussiones Mathematicae Graph Theory
|
2012
|
tom 32
|
nr 2
263-270
EN
Let G = (V,E) be a graph. A subset S of V is a 2-dominating set if every vertex of V-S is dominated at least 2 times, and S is a 2-independent set of G if every vertex of S has at most one neighbor in S. The minimum cardinality of a 2-dominating set a of G is the 2-domination number γ₂(G) and the maximum cardinality of a 2-independent set of G is the 2-independence number β₂(G). Fink and Jacobson proved that γ₂(G) ≤ β₂(G) for every graph G. In this paper we provide a constructive characterization of trees with equal 2-domination and 2-independence numbers.
9
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Maximal k-independent sets in graphs

52%
Blidia M., Chellali M., Favaron O., Meddah N.
Discussiones Mathematicae Graph Theory
|
2008
|
tom 28
|
nr 1
151-163
EN
A subset of vertices of a graph G is k-independent if it induces in G a subgraph of maximum degree less than k. The minimum and maximum cardinalities of a maximal k-independent set are respectively denoted iₖ(G) and βₖ(G). We give some relations between βₖ(G) and $β_j(G)$ and between iₖ(G) and $i_j(G)$ for j ≠ k. We study two families of extremal graphs for the inequality i₂(G) ≤ i(G) + β(G). Finally we give an upper bound on i₂(G) and a lower bound when G is a cactus.
10
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Bounds on the global offensive k-alliance number in graphs

52%
Chellali M., Haynes T., Randerath B., Volkmann L.
Discussiones Mathematicae Graph Theory
|
2009
|
tom 29
|
nr 3
597-613
EN
Let G = (V(G),E(G)) be a graph, and let k ≥ 1 be an integer. A set S ⊆ V(G) is called a global offensive k-alliance if |N(v)∩S| ≥ |N(v)-S|+k for every v ∈ V(G)-S, where N(v) is the neighborhood of v. The global offensive k-alliance number $γₒ^k(G)$ is the minimum cardinality of a global offensive k-alliance in G. We present different bounds on $γₒ^k(G)$ in terms of order, maximum degree, independence number, chromatic number and minimum degree.
11
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

Exact double domination in graphs

52%
Chellali M., Khelladi A., Maffray F.
Discussiones Mathematicae Graph Theory
|
2005
|
tom 25
|
nr 3
291-302
EN
In a graph a vertex is said to dominate itself and all its neighbours. A doubly dominating set of a graph G is a subset of vertices that dominates every vertex of G at least twice. A doubly dominating set is exact if every vertex of G is dominated exactly twice. We prove that the existence of an exact doubly dominating set is an NP-complete problem. We show that if an exact double dominating set exists then all such sets have the same size, and we establish bounds on this size. We give a constructive characterization of those trees that admit a doubly dominating set, and we establish a necessary and sufficient condition for the existence of an exact doubly dominating set in a connected cubic graph.
12
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On locating-domination in graphs

52%
Chellali M., Mimouni M., Slater P.
Discussiones Mathematicae Graph Theory
|
2010
|
tom 30
|
nr 2
223-235
EN
A set D of vertices in a graph G = (V,E) is a locating-dominating set (LDS) if for every two vertices u,v of V-D the sets N(u)∩ D and N(v)∩ D are non-empty and different. The locating-domination number $γ_L(G)$ is the minimum cardinality of a LDS of G, and the upper locating-domination number, $Γ_L(G)$ is the maximum cardinality of a minimal LDS of G. We present different bounds on $Γ_L(G)$ and $γ_L(G)$.
13
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

k-independence stable graphs upon edge removal

52%
Chellali M., Haynes T., Volkmann L.
Discussiones Mathematicae Graph Theory
|
2010
|
tom 30
|
nr 2
265-274
EN
Let k be a positive integer and G = (V(G),E(G)) a graph. A subset S of V(G) is a k-independent set of G if the subgraph induced by the vertices of S has maximum degree at most k-1. The maximum cardinality of a k-independent set of G is the k-independence number βₖ(G). A graph G is called β¯ₖ-stable if βₖ(G-e) = βₖ(G) for every edge e of E(G). First we give a necessary and sufficient condition for β¯ₖ-stable graphs. Then we establish four equivalent conditions for β¯ₖ-stable trees.
14
Artykuł dostępny w postaci pełnego tekstu - kliknij by otworzyć plik
Content available

On the p-domination number of cactus graphs

52%
Blidia M., Chellali M., Volkmann L.
Discussiones Mathematicae Graph Theory
|
2005
|
tom 25
|
nr 3
355-361
EN
Let p be a positive integer and G = (V,E) a graph. A subset S of V is a p-dominating set if every vertex of V-S is dominated at least p times. The minimum cardinality of a p-dominating set a of G is the p-domination number γₚ(G). It is proved for a cactus graph G that γₚ(G) ⩽ (|V| + |Lₚ(G)| + c(G))/2, for every positive integer p ⩾ 2, where Lₚ(G) is the set of vertices of G of degree at most p-1 and c(G) is the number of odd cycles in G.
first rewind previous Strona / 1 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ć.