Currently displaying 1 – 16 of 16

Showing per page

Order by Relevance | Title | Year of publication

On locating and differentiating-total domination in trees

Mustapha Chellali — 2008

Discussiones Mathematicae Graph Theory

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

Trees with equal 2-domination and 2-independence numbers

Mustapha ChellaliNacéra Meddah — 2012

Discussiones Mathematicae Graph Theory

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

Double domination critical and stable graphs upon vertex removal

Soufiane KhelifiMustapha Chellali — 2012

Discussiones Mathematicae Graph Theory

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

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

Mustapha ChellaliLutz Volkmann — 2011

Discussiones Mathematicae Graph Theory

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.

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

Mustapha ChellaliNader Jafari Rad — 2013

Discussiones Mathematicae Graph Theory

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

On the p-domination number of cactus graphs

Mostafa BlidiaMustapha ChellaliLutz Volkmann — 2005

Discussiones Mathematicae Graph Theory

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.

Exact double domination in graphs

Mustapha ChellaliAbdelkader KhelladiFrédéric Maffray — 2005

Discussiones Mathematicae Graph Theory

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

On the dominator colorings in trees

Houcine Boumediene MerouaneMustapha Chellali — 2012

Discussiones Mathematicae Graph Theory

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

Global alliances and independence in trees

Mustapha ChellaliTeresa W. Haynes — 2007

Discussiones Mathematicae Graph Theory

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

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

Mustapha ChellaliEl hassane Fliouet — 2011

Colloquium Mathematicae

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

Extensions purement inséparables d'exposant non borné

Mustapha ChellaliEl Hasane Fliouet — 2004

Archivum Mathematicum

Dans [Swe], Sweedler a caractérisé les extensions purement inséparables K / k d’exposant fini qui sont produit tensoriel d’extensions simples. En vue d’étendre ce résultat aux extensions d’exposants non bornés, L. Kime dans [Kim] propose les extensions k ( x p - ) = k ( x p - 1 , x p - 2 , ) comme généralisation d’extensions simples. Dans ce travail, on propose d’autres généralisations naturelles. Ceci nous a permis de décrire explicitement toutes les extensions purement inséparables K / k lorsque le degré d’imperfection de k est 2 . Dans [Dev2]...

On locating-domination in graphs

Mustapha ChellaliMalika MimouniPeter J. Slater — 2010

Discussiones Mathematicae Graph Theory

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

Bounds on the global offensive k-alliance number in graphs

Mustapha ChellaliTeresa W. HaynesBert RanderathLutz Volkmann — 2009

Discussiones Mathematicae Graph Theory

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.

Maximal k-independent sets in graphs

Mostafa BlidiaMustapha ChellaliOdile FavaronNacéra Meddah — 2008

Discussiones Mathematicae Graph Theory

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.

k-independence stable graphs upon edge removal

Mustapha ChellaliTeresa W. HaynesLutz Volkmann — 2010

Discussiones Mathematicae Graph Theory

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.

Page 1

Download Results (CSV)