An edge of a graph is called dot-critical if its contraction decreases the domination number. A graph is said to be dot-critical if all of its edges are dot-critical. A vertex of a graph is called critical if its deletion decreases the domination number. In A note on the domination dot-critical graphs, Discrete Appl. Math. 157 (2009) 3743-3745, Chen and Shiu constructed for each even integer k ≥ 4 infinitely many k-dot-critical graphs G with no critical vertices and k(G) = 1. In this paper, we refine...

In this paper we continue the study of paired-domination in graphs introduced by Haynes and Slater (Networks 32 (1998), 199–206). A paired-dominating set of a graph $G$ with no isolated vertex is a dominating set of vertices whose induced subgraph has a perfect matching. The paired-domination number of $G$, denoted by ${\gamma }_{\mathrm{pr}}\left(G\right)$, is the minimum cardinality of a paired-dominating set of $G$. The graph $G$ is paired-domination vertex critical if for every vertex $v$ of $G$ that is not adjacent to a vertex of degree one,...

Let k be a positive integer, and let G be a simple graph with vertex set V (G). A k-distance Roman dominating function on G is a labeling f : V (G) → {0, 1, 2} such that for every vertex with label 0, there is a vertex with label 2 at distance at most k from each other. The weight of a k-distance Roman dominating function f is the value w(f) =∑v∈V f(v). The k-distance Roman domination number of a graph G, denoted by γkR (D), equals the minimum weight of a k-distance Roman dominating function on...

Let K3n denote the Cartesian product Kn□Kn□Kn, where Kn is the complete graph on n vertices. We show that the domination number of K3n is [...]

The edge C₄ graph of a graph G, E₄(G) is a graph whose vertices are the edges of G and two vertices in E₄(G) are adjacent if the corresponding edges in G are either incident or are opposite edges of some C₄. In this paper, we show that there exist infinitely many pairs of non isomorphic graphs whose edge C₄ graphs are isomorphic. We study the relationship between the diameter, radius and domination number of G and those of E₄(G). It is shown that for any graph G without isolated vertices, there...

We prove a two-point concentration for the independent domination number of the random graph $G_{n,p}$ provided p²ln(n) ≥ 64ln((lnn)/p).

For an ordered set $W=\{w_1,w_2,\cdots ,w_k\}$ of vertices in a connected graph $G$ and a vertex $v$ of $G$, the code of $v$ with respect to $W$ is the $k$-vector $$c_W\left(v\right)=(d(v,w_1),d(v,w_2),\cdots ,d(v,w_k)).$$ The set $W$ is an independent resolving set for $G$ if (1) $W$ is independent in $G$ and (2) distinct vertices have distinct codes with respect to $W$. The cardinality of a minimum independent resolving set in $G$ is the independent resolving number $\mathrm{i}r\left(G\right)$. We study the existence of independent resolving sets in graphs, characterize all nontrivial connected graphs $G$ of order $n$ with $\mathrm{i}r\left(G\right)=1$, $n-1$,...

Let $k$ be a positive integer, and let $G$ be a simple graph with vertex set $V\left(G\right)$. A $k$-dominating set of the graph $G$ is a subset $D$ of $V\left(G\right)$ such that every vertex of $V\left(G\right)-D$ is adjacent to at least $k$ vertices in $D$. A $k$-domatic partition of $G$ is a partition of $V\left(G\right)$ into $k$-dominating sets. The maximum number of dominating sets in a $k$-domatic partition of $G$ is called the $k$-domatic number$d_k\left(G\right)$. In this paper, we present upper and lower bounds for the $k$-domatic number, and we establish Nordhaus-Gaddum-type results. Some of...

Let D = (V,A) be a finite and simple digraph. A k-rainbow dominating function (kRDF) of a digraph D is a function f from the vertex set V to the set of all subsets of the set {1, 2, . . . , k} such that for any vertex v ∈ V with f(v) = Ø the condition ∪u∈N−(v) f(u) = {1, 2, . . . , k} is fulfilled, where N−(v) is the set of in-neighbors of v. The weight of a kRDF f is the value w(f) = ∑v∈V |f(v)|. The k-rainbow domination number of a digraph D, denoted by γrk(D), is the minimum weight of a kRDF...

For a positive integer k, a k-rainbow dominating function of a graph G is a function f from the vertex set V(G) to the set of all subsets of the set 1,2, ...,k such that for any vertex v ∈ V(G) with f(v) = ∅ the condition ⋃u ∈ N(v)f(u) = 1,2, ...,k is fulfilled, where N(v) is the neighborhood of v. The 1-rainbow domination is the same as the ordinary domination. A set $f₁,f₂,...,f_d$ of k-rainbow dominating functions on G with the property that ${\sum }_{i=1}^d\left|f_i\left(v\right)\right|\le k$ for each v ∈ V(G), is called a k-rainbow dominating family (of...

Lower and upper bounds are obtained for the clique number $\omega \left(G\right)$ and the independence number $\alpha \left(G\right)$, in terms of the eigenvalues of the signless Laplacian matrix of a graph $G$.