Wyniki wyszukiwania - BazTech

1

Criticality indices of 2-rainbow domination of paths and cycles

Bouchou A., Blidia M.

Opuscula Mathematica

|

2016

|

Vol. 36, no. 5

563-–574

EN

A 2-rainbow dominating function of a graph G (V(G), E(G)) is a function ƒ that assigns to each vertex a set of colors chosen from the set {1,2} so that for each vertex with ƒ (v) = ∅ we have [formula].The weight of a 2RDF ƒ is defined as [formula] minimum weight of a 2RDF is called the 2-rainbow domination number of G, denoted by [formula].The vertex criticality index of a 2-rainbow domination of a graph G is defined as [formula] the edge removal criticality index of a 2-rainbow domination of a graph G is defined as [formula] and the edge addition of a 2-rainbow domination criticality index of G is defined as [formula] where G is the complement graph of G. In this paper, we determine the criticality indices of paths and cycles.

2

On b-vertex and b-edge critical graphs

Eschouf N. I., Blidia M.

Opuscula Mathematica

|

2015

|

Vol. 35, no. 2

171--180

EN

A b-coloring is a coloring of the vertices of a graph such that each color class contains a vertex that has a neighbor in all other color classes, and the b-chromatic number b(G) of a graph G is the largest integer k such that G admits a b-coloring with k colors. A simple graph G is called b+-vertex (edge) critical if the removal of any vertex (edge) of G increases its b-chromatic number. In this note, we explain some properties in b+-vertex (edge) critical graphs, and we conclude with two open problems.

3

On vertex b-critical trees

Blidia M., Eschouf N. I., Maffray F.

Opuscula Mathematica

|

2013

|

Vol. 33, no. 1

19-28

EN

A b-coloring is a proper coloring of the vertices of a graph such that each color class has a vertex that has neighbors of all other colors. The b-chromatic number of a graph G is the largest k such that G admits a b-coloring with k colors. A graph G is b-critical if the removal of any vertex of G decreases the b-chromatic number. We prove various properties of b-critical trees. In particular, we characterize b-critical trees.

4

A note on k-Roman graphs

Bouchou A., Blidia M., Chellali M.

Opuscula Mathematica

|

2013

|

Vol. 33, no. 4

641--646

EN

Let G = (V,E) be a graph and let k be a positive integer. A subset D of V (G) is a k-dominating set of G if every vertex in V (G) \D has at least k neighbours in D. The k-domination number Υk(G) is the minimum cardinality of a k-dominating set of G. A Roman k-dominating function on G is a function f : V (G) →{0, 1, 2} such that every vertex u for which f(u) = 0 is adjacent to at least k vertices v1, v2, . . . , vk with f(vi) = 2 for i = 1, 2, . . . , k. The weight of a Roman k-dominating function is the value [formula] and the minimum weight of a Roman k-dominating function on G is called the Roman k-domination number Υk(G) of G. A graph G is said to be a k-Roman graph if ΥkR(G) = 2Υk(G) . In this note we study k-Roman graphs.

5

Vertices belonging to all or to no minimum locating dominating sets of trees

Blidia M., Lounes R.

Opuscula Mathematica

|

2009

|

Vol. 29, no. 1

5-14

EN

A set D of vertices in a graph G is a locating-dominating set if for every two vertices u, v of G \ D the sets N(u) ∩ D and N (v) ∩ D are non-empty and different. In this paper, we characterize vertices that are in all or in no minimum locating dominating sets in trees. The characterization guarantees that the γL-excellent tree can be recognized in a polynomial time.

6

A note on Vizing's generalized conjecture

Blidia M., Chellali M.

Opuscula Mathematica

|

2007

|

Vol. 27, no. 2

181-185

EN

In this note we give a generalized version of Vizing's conjecture concerning the distance domination number for the cartesian product of two graphs.