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