The signed total domination number of a graph is a certain variant of the domination number. If $v$ is a vertex of a graph $G$, then $N\left(v\right)$ is its oper neighbourhood, i.e. the set of all vertices adjacent to $v$ in $G$. A mapping $f:V\left(G\right)\to \{-1,1\}$, where $V\left(G\right)$ is the vertex set of $G$, is called a signed total dominating function (STDF) on $G$, if ${\sum }_{x\in N\left(v\right)}f\left(x\right)\ge 1$ for each $v\in V\left(G\right)$. The minimum of values ${\sum }_{x\in V\left(G\right)}f\left(x\right)$, taken over all STDF’s of $G$, is called the signed total domination number of $G$ and denoted by ${\gamma }_{\mathrm{s}t}\left(G\right)$. A theorem stating lower bounds for ${\gamma }_{\mathrm{s}t}\left(G\right)$ is...

The paper solves one problem by E. Prisner concerning the 2-distance operator T₂. This is an operator on the class $C_f$ of all finite undirected graphs. If G is a graph from $C_f$, then T₂(G) is the graph with the same vertex set as G in which two vertices are adjacent if and only if their distance in G is 2. E. Prisner asks whether the periodicity ≥ 3 is possible for T₂. In this paper an affirmative answer is given. A result concerning the periodicity 2 is added.

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.

Given a graph G, its partially square graph G* is a graph obtained by adding an edge (u,v) for each pair u, v of vertices of G at distance 2 whenever the vertices u and v have a common neighbor x satisfying the condition $N_G\left(x\right)\subseteq N_G\left[u\right]\cup N_G\left[v\right]$, where $N_G\left[x\right]=N_G\left(x\right)\cup x$. In the case where G is a claw-free graph, G* is equal to G². We define $\sigma °ₜ=min{\sum }_{x\in S}{d}_G\left(x\right):SisanindependentsetinG*and\left|S\right|=t$. We give for hamiltonicity and circumference new sufficient conditions depending on σ° and we improve some known results.

One of numerical invariants concerning domination in graphs is the $k$-subdomination number ${\gamma }_{kS}^{-11}\left(G\right)$ of a graph $G$. A conjecture concerning it was expressed by J. H. Hattingh, namely that for any connected graph $G$ with $n$ vertices and any $k$ with $\frac{1}{2}n<k\leqq n$ the inequality ${\gamma }_{kS}^{-11}\left(G\right)\leqq 2k-n$ holds. This paper presents a simple counterexample which disproves this conjecture. This counterexample is the graph of the three-dimensional cube and $k=5$.

A graph $G$ is a $\{d,d+k\}$-graph, if one vertex has degree $d+k$ and the remaining vertices of $G$ have degree $d$. In the special case of $k=0$, the graph $G$ is $d$-regular. Let $k,p\ge 0$ and $d,n\ge 1$ be integers such that $n$ and $p$ are of the same parity. If $G$ is a connected $\{d,d+k\}$-graph of order $n$ without a matching $M$ of size $2\left|M\right|=n-p$, then we show in this paper the following: If $d=2$, then $k\ge 2(p+2)$ and (i) $n\ge k+p+6$. If $d\ge 3$ is odd and $t$ an integer with $1\le t\le p+2$, then (ii) $n\ge d+k+1$ for $k\ge d(p+2)$, (iii) $n\ge d(p+3)+2t+1$ for $d(p+2-t)+t\le k\le d(p+3-t)+t-3$, (iv) $n\ge d(p+3)+2p+7$ for $k\le p$. If $d\ge 4$ is even, then (v) $n\ge d+k+2-\eta$ for $k\ge d(p+3)+p+4+\eta$, (vi) $n\ge d+k+p+2-2t=d(p+4)+p+6$ for $k=d(p+3)+4+2t$ and $p\ge 1$,...

The independent domination number $i\left(G\right)$ (independent number $\beta \left(G\right)$) is the minimum (maximum) cardinality among all maximal independent sets of $G$. Haviland (1995) conjectured that any connected regular graph $G$ of order $n$ and degree $\delta \le \frac{1}{2}n$ satisfies $i\left(G\right)\le \lceil \frac{2n}{3\delta }\rceil \frac{1}{2}\delta$. For $1\le k\le l\le m$, the subset graph $S_m(k,l)$ is the bipartite graph whose vertices are the $k$- and $l$-subsets of an $m$ element ground set where two vertices are adjacent if and only if one subset is contained in the other. In this paper, we give a sharp upper bound for $i\left(S_m(k,l)\right)$ and...