>We prove that the domination number γ(T) of a tree T on n ≥ 3 vertices and with n₁ endvertices satisfies inequality γ(T) ≥ (n+2-n₁)/3 and we characterize the extremal graphs.

In this note, we prove several lower bounds on the domination number of simple connected graphs. Among these are the following: the domination number is at least two-thirds of the radius of the graph, three times the domination number is at least two more than the number of cut-vertices in the graph, and the domination number of a tree is at least as large as the minimum order of a maximal matching.

The open neighborhood $N_G\left(e\right)$ of an edge $e$ in a graph $G$ is the set consisting of all edges having a common end-vertex with $e$. Let $f$ be a function on $E\left(G\right)$, the edge set of $G$, into the set $\{-1,1\}$. If ${\sum }_{x\in N_G\left(e\right)}f\left(x\right)\ge 1$ for each $e\in E\left(G\right)$, then $f$ is called a signed edge total dominating function of $G$. The minimum of the values ${\sum }_{e\in E\left(G\right)}f\left(e\right)$, taken over all signed edge total dominating function $f$ of $G$, is called the signed edge total domination number of $G$ and is denoted by ${\gamma }_{st}^{\text{'}}\left(G\right)$. Obviously, ${\gamma }_{st}^{\text{'}}\left(G\right)$ is defined only for graphs $G$ which have no connected components...

A set S of vertices of a graph G = (V,E) without isolated vertex is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. The total domination number γₜ(G) is the minimum cardinality of a total dominating set of G. The total domination subdivision number $s{d}_{\gamma ₜ\left(G\right)}$ is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the total domination number. Favaron, Karami, Khoeilar and Sheikholeslami (Journal of Combinatorial...

In set theory without the axiom of choice (AC), we observe new relations of the following statements with weak choice principles. $\circ$${𝒫}_{\mathrm{lf},\mathrm{c}}$

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 ${\beta }_j\left(G\right)$ and between iₖ(G) and $i_j\left(G\right)$ 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.

The direct product of graphs G = (V (G),E(G)) and H = (V (H),E(H)) is the graph, denoted as G×H, with vertex set V (G×H) = V (G)×V (H), where vertices (x1, y1) and (x2, y2) are adjacent in G × H if x1x2 ∈ E(G) and y1y2 ∈ E(H). Let n be odd and m even. We prove that every maximum independent set in Pn×G, respectively Cm×G, is of the form (A×C)∪(B× D), where C and D are nonadjacent in G, and A∪B is the bipartition of Pn respectively Cm. We also give a characterization of maximum independent subsets...

The mean value of the matching polynomial is computed in the family of all labeled graphs with n vertices. We introduce the dominating polynomial of a graph whose coefficients enumerate the dominating sets for a graph and study some properties of the polynomial. The mean value of this polynomial is determined in a certain special family of bipartite digraphs.

We provide an algorithm for listing all minimal 2-dominating sets of a tree of order n in time 𝒪(1.3248n). This implies that every tree has at most 1.3248n minimal 2-dominating sets. We also show that this bound is tight.

The paper studies minimal acyclic dominating sets, acyclic domination number and upper acyclic domination number in graphs having cut-vertices.

A three-valued function $fV\to \{-1,0,1\}$ defined on the vertices of a graph $G=(V,E)$ is a minus total dominating function (MTDF) if the sum of its function values over any open neighborhood is at least one. That is, for every $v\in V$, $f\left(N\right(v\left)\right)\ge 1$, where $N\left(v\right)$ consists of every vertex adjacent to $v$. The weight of an MTDF is $f\left(V\right)=\sum f\left(v\right)$, over all vertices $v\in V$. The minus total domination number of a graph $G$, denoted ${\gamma }_t^{-}\left(G\right)$, equals the minimum weight of an MTDF of $G$. In this paper, we discuss some properties of minus total domination on a graph $G$ and obtain...

A dominating broadcast on a graph G = (V, E) is a function f: V → {0, 1, ..., diam G} such that f(v) ≤ e(v) (the eccentricity of v) for all v ∈ V and such that each vertex is within distance f(v) from a vertex v with f(v) > 0. The cost of a broadcast f is σ(f) = Σv∈V f(v), and the broadcast number λ b (G) is the minimum cost of a dominating broadcast. A set X ⊆ V(G) is said to be irredundant if each x ∈ X dominates a vertex y that is not dominated by any other vertex in X; possibly y = x. The...

In this paper, we study the signed total domination number in graphs and present new sharp lower and upper bounds for this parameter. For example by making use of the classic theorem of Turán [8], we present a sharp lower bound on Kr+1-free graphs for r ≥ 2. Applying the concept of total limited packing we bound the signed total domination number of G with δ(G) ≥ 3 from above by [...] . Also, we prove that γst(T) ≤ n − 2(s − s′) for any tree T of order n, with s support vertices and s′ support vertices...

Nordhaus-Gaddum results for weakly convex domination number of a graph G are studied.

In this note the split domination number of the Cartesian product of two paths is considered. Our results are related to [2] where the domination number of Pₘ ☐ Pₙ was studied. The split domination number of P₂ ☐ Pₙ is calculated, and we give good estimates for the split domination number of Pₘ ☐ Pₙ expressed in terms of its domination number.

Every connected graph G with radius r(G) and independence number α(G) obeys α(G) ≥ r(G). Recently the graphs for which equality holds have been classified. Here we investigate the members of this class that are Cartesian products. We show that for non-trivial graphs G and H, α(G ☐ H) = r(G ☐ H) if and only if one factor is a complete graph on two vertices, and the other is a nontrivial complete graph. We also prove a new (polynomial computable) lower bound α(G ☐ H) ≥ 2r(G)r(H) for the independence...

Let G = (V,E) be a simple, undirected graph. A set of vertices D is called an odd dominating set if |N[v] ∩ D| ≡ 1 (mod 2) for every vertex v ∈ V(G). The minimum cardinality of an odd dominating set is called the odd domination number of G, denoted by γ₁(G). In this paper, several algorithmic and structural results are presented on this parameter for grids, complements of powers of cycles, and other graph classes as well as for more general forms of "residue" domination.