Consider an arc-colored digraph. A set of vertices N is a kernel by monochromatic paths if all pairs of distinct vertices of N have no monochromatic directed path between them and if for every vertex v not in N there exists n ∈ N such that there is a monochromatic directed path from v to n. In this paper we prove different sufficient conditions which imply that an arc-colored tournament has a kernel by monochromatic paths. Our conditions concerns to some subdigraphs of T and its quasimonochromatic...

For a graph G, a positive integer k, k ≥ 2, and a non-negative integer with z < k and z ≠ 1, a subset D of the vertex set V(G) is said to be a non-z (mod k) dominating set if D is a dominating set and for all x ∈ V(G), |N[x]∩D| ≢ z (mod k).For the case k = 2 and z = 0, it has been shown that these sets exist for all graphs. The problem for k ≥ 3 is unknown (the existence for even values of k and z = 0 follows from the k = 2 case.) It is the purpose of this paper to show that for k ≥ 3 and with...

We consider sequential heuristics methods for the Maximum Independent Set (MIS) problem. Three classical algorithms, VO [11], MIN [12], or MAX [6] , are revisited. We combine Algorithm MIN with the α-redundant vertex technique[3]. Induced forbidden subgraph sets, under which the algorithms give maximum independent sets, are described. The Caro-Wei bound [4,14] is verified and performance of the algorithms on some special graphs is considered.

The signed distance-$k$-domination number of a graph is a certain variant of the signed domination number. If $v$ is a vertex of a graph $G$, the open $k$-neighborhood of $v$, denoted by $N_k\left(v\right)$, is the set $N_k\left(v\right)=\{u\mid u\ne v$ and $d(u,v)\le k\}$. $N_k\left[v\right]=N_k\left(v\right)\cup \left\{v\right\}$ is the closed $k$-neighborhood of $v$. A function $fV\to \{-1,1\}$ is a signed distance-$k$-dominating function of $G$, if for every vertex $v\in V$, $f\left(N_k\left[v\right]\right)={\sum }_{u\in N_k\left[v\right]}f\left(u\right)\ge 1$. The signed distance-$k$-domination number, denoted by ${\gamma }_{k,s}\left(G\right)$, is the minimum weight of a signed distance-$k$-dominating function on $G$. The values of ${\gamma }_{2,s}\left(G\right)$ are found for graphs with small diameter,...

The signed edge domination number of a graph is an edge variant of the signed domination number. The closed neighbourhood $N_G\left[e\right]$ of an edge $e$ in a graph $G$ is the set consisting of $e$ and of all edges having a common end vertex with $e$. Let $f$ be a mapping of the edge set $E\left(G\right)$ of $G$ into the set $\{-1,1\}$. If ${\sum }_{x\in N\left[e\right]}f\left(x\right)\ge 1$ for each $e\in E\left(G\right)$, then $f$ is called a signed edge dominating function on $G$. The minimum of the values ${\sum }_{x\in E\left(G\right)}f\left(x\right)$, taken over all signed edge dominating function $f$ on $G$, is called the signed edge domination number of $G$ and is...

A graph G is 2-stratified if its vertex set is partitioned into two classes (each of which is a stratum or a color class), 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 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...

We consider, for a positive integer $k$, induced subgraphs in which each component has order at most $k$. Such a subgraph is said to be $k$-divided. We show that finding large induced subgraphs with this property is NP-complete. We also consider a related graph-coloring problem: how many colors are required in a vertex coloring in which each color class induces a $k$-divided subgraph. We show that the problem of determining whether some given number of colors suffice is NP-complete, even for $2$-coloring...

Let γ(G) and ${\gamma }_{2,2}\left(G\right)$ 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 $\left(2(\gamma \left(T\right)+1)\right)/3\le {\gamma }_{2,2}\left(T\right)\le 2\gamma \left(T\right)$. Moreover, we characterize all the trees achieving the equalities.

Let $G=(V_G,E_G)$ be a graph and let $N_G\left[v\right]$ denote the closed neighbourhood of a vertex $v$ in $G$. A function $f:V_G\to \{-1,0,1\}$ is said to be a balanced dominating function (BDF) of $G$ if ${\sum }_{u\in N_G\left[v\right]}f\left(u\right)=0$ holds for each vertex $v\in V_G$. The balanced domination number of $G$, denoted by ${\gamma }_b\left(G\right)$, is defined as $${\gamma }_b\left(G\right)=max\left\{\sum _{v\in V_G}f\left(v\right):f\text{is}\text{a}\text{BDF}\text{of}G\right\}.$$ A graph $G$ is called $d$-balanced if ${\gamma }_b\left(G\right)=0$. The novel concept of balanced domination for graphs is introduced. Some upper bounds on the balanced domination number are established, in which one is the best possible bound and the rest are sharp, all the corresponding...

We show that the decision problem for p-reinforcement, p-total rein- forcement, total restrained reinforcement, and k-rainbow reinforcement are NP-hard for bipartite graphs.

For a permutation π of the vertex set of a graph G, the graph π G is obtained from two disjoint copies G₁ and G₂ of G by joining each v in G₁ to π(v) in G₂. Hence if π = 1, then πG = K₂×G, the prism of G. Clearly, γ(G) ≤ γ(πG) ≤ 2 γ(G). We study graphs for which γ(K₂×G) = 2γ(G), those for which γ(πG) = 2γ(G) for at least one permutation π of V(G) and those for which γ(πG) = 2γ(G) for each permutation π of V(G).

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

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

For a given connected graph G = (V, E), a set $$D\subseteq V\left(G\right)$$ is a doubly connected dominating set if it is dominating and both 〈D〉 and 〈V (G)-D〉 are connected. The cardinality of the minimum doubly connected dominating set in G is the doubly connected domination number. We investigate several properties of doubly connected dominating sets and give some bounds on the doubly connected domination number.

In 1968, Vizing conjectured that for any edge chromatic critical graph G = (V,E) with maximum degree △ and independence number α (G), α (G) ≤ [...] . It is known that α (G) < [...] |V |. In this paper we improve this bound when △≥ 4. Our precise result depends on the number n2 of 2-vertices in G, but in particular we prove that α (G) ≤ [...] |V | when △ ≥ 5 and n2 ≤ 2(△− 1)

Let $G=(V,E)$ be a simple graph. A $3$-valued function $fV\left(G\right)\to \{-1,0,1\}$ is said to be a minus dominating function if for every vertex $v\in V$, $f\left(N\left[v\right]\right)={\sum }_{u\in N\left[v\right]}f\left(u\right)\ge 1$, where $N\left[v\right]$ is the closed neighborhood of $v$. The weight of a minus dominating function $f$ on $G$ is $f\left(V\right)={\sum }_{v\in V}f\left(v\right)$. The minus domination number of a graph $G$, denoted by ${\gamma }^{-}\left(G\right)$, equals the minimum weight of a minus dominating function on $G$. In this paper, the following two results are obtained. (1) If $G$ is a bipartite graph of order $n$, then $${\gamma }^{-}\left(G\right)\ge 4\left(\sqrt{n+1}-1\right)-n.$$ (2) For any negative integer $k$ and any positive integer $m\ge 3$, there exists...