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.

Two classes of graphs which are maximal with respect to the absence of Hamiltonian paths are presented. Block graphs with this property are characterized.

A simplex of a graph G is a subgraph of G which is a complete graph. The simplex graph Simp(G) of G is the graph whose vertex set is the set of all simplices of G and in which two vertices are adjacent if and only if they have a non-empty intersection. The simplex graph operator is the operator which to every graph G assigns its simplex graph Simp(G). The paper studies graphs which are fixed in this operator and gives a partial answer to a problem suggested by E. Prisner.

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 stated for the...

The domatic numbers of a graph $G$ and of its complement $\overline{G}$ were studied by J. E. Dunbar, T. W. Haynes and M. A. Henning. They suggested four open problems. We will solve the following ones: Characterize bipartite graphs $G$ having $d\left(G\right)=d\left(\overline{G}\right)$. Further, we will present a partial solution to the problem: Is it true that if $G$ is a graph satisfying $d\left(G\right)=d\left(\overline{G}\right)$, then $\gamma \left(G\right)=\gamma \left(\overline{G}\right)$? Finally, we prove an existence theorem concerning the total domatic number of a graph and of its complement.

Generalized Petersen graphs are certain graphs consisting of one quadratic factor. For these graphs some numerical invariants concerning the domination are studied, namely the domatic number $d\left(G\right)$, the total domatic number ${d}_{t}\left(G\right)$ and the $k$-ply domatic number ${d}^{k}\left(G\right)$ for $k=2$ and $k=3$. Some exact values and some inequalities are stated.

The signed edge domination number and the signed total edge domination number of a graph are considered; they are variants of the domination number and the total domination number. Some upper bounds for them are found in the case of the $n$-dimensional cube ${Q}_{n}$.

The paper studies the signed domination number and the minus domination number of the complete bipartite graph ${K}_{p,q}$.

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

Download Results (CSV)