Using multilinear functions and random procedures, new upper bounds on the domination number of a bipartite graph in terms of the cardinalities and the minimum degrees of the two colour classes are established.

A graph is $2$-stratified if its vertex set is partitioned into two classes, where the vertices in one class are colored red and those in the other class are colored blue. Let $F$ be a $2$-stratified graph rooted at some blue vertex $v$. An $F$-coloring of a graph $G$ is a red-blue coloring of the vertices of $G$ in which every blue vertex $v$ belongs to a copy of $F$ rooted at $v$. The $F$-domination number ${\gamma }_F\left(G\right)$ is the minimum number of red vertices in an $F$-coloring of $G$. In this paper, we study $F$-domination where $F$ is...

On étudie à l'aide du système AutoGraphiX 2 (AGX 2) des relations de la forme $${\underline{b}}_n\le g\oplus i\le {\overline{b}}_n$$ où g désigne la maille d'un graphe G=(V, E), i un autre invariant parmi la distance moyenne $\overline{l}$, l'index λ1, l'indice de Randić R et le nombre de domination β, $\oplus$ désigne l'une des opérations +, -, ×, /, ${\underline{b}}_n$ et ${\overline{b}}_n$ des fonctions de l'ordre n du graphe qui bornent l'expression $g\oplus i$ et sont atteintes pour tout n (sauf éventuellement de très petites valeurs du fait des effets de bord). Les résultats prouvés ou discutés ci-dessous...

In this paper we show upper bounds for the sum and the product of the lower domination parameters and the chromatic index of a graph. We also present some families of graphs for which these upper bounds are achieved. Next, we give a lower bound for the sum of the upper domination parameters and the chromatic index. This lower bound is a function of the number of vertices of a graph and a new graph parameter which is defined here. In this case we also characterize graphs for which a respective equality...

Dynamic monopolies in graphs have been studied as a model for spreading processes within networks. Together with their dual notion, the generalized degenerate sets, they form the immediate generalization of the classical notions of vertex covers and independent sets in a graph. We present results concerning dynamic monopolies in graphs of given average threshold values extending and generalizing previous results of Khoshkhah et al. [On dynamic monopolies of graphs: The average and strict majority...

The restrained domination number ${\gamma }^r\left(G\right)$ and the total restrained domination number ${\gamma }_t^r\left(G\right)$ of a graph $G$ were introduced recently by various authors as certain variants of the domination number $\gamma \left(G\right)$ of $\left(G\right)$. A well-known numerical invariant of a graph is the domatic number $d\left(G\right)$ which is in a certain way related (and may be called dual) to $\gamma \left(G\right)$. The paper tries to define analogous concepts also for the restrained domination and the total restrained domination and discusses the sense of such new definitions.

For an ordered set $W=\{w_1,w_2,\cdots ,w_k\}$ of vertices and a vertex $v$ in a connected graph $G$, the (metric) representation of $v$ with respect to $W$ is the $k$-vector $r\left(v\right|W)=(d(v,w_1),d(v,w_2),\cdots ,d(v,w_k))$, where $d(x,y)$ represents the distance between the vertices $x$ and $y$. The set $W$ is a resolving set for $G$ if distinct vertices of $G$ have distinct representations with respect to $W$. A resolving set of minimum cardinality is called a minimum resolving set or a basis and the cardinality of a basis for $G$ is its dimension $dimG$. A set $S$ of vertices in $G$ is a dominating set...

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 ${\gamma }_r\left(G\right)$, 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 ${\gamma }_r\left(U\right)\ge ⎡n/3⎤$, and provide a characterization of graphs achieving this bound.

A Roman dominating function on a graph G is a function f:V(G) → 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 a Roman dominating function is the value $f\left(V\left(G\right)\right)={\sum }_{u\in V\left(G\right)}f\left(u\right)$. The Roman domination number, ${\gamma }_R\left(G\right)$, of G is the minimum weight of a Roman dominating function on G. In this paper, we define the Roman bondage $b_R\left(G\right)$ of a graph G with maximum degree at least two to be the minimum cardinality of all sets E’ ⊆ E(G) for which ${\gamma }_R(G-E^{\text{'}})>{\gamma }_R\left(G\right)$....