The symbol K(B,C) denotes a directed graph with the vertex set B∪C for two (not necessarily disjoint) vertex sets B,C in which an arc goes from each vertex of B into each vertex of C. A subdigraph of a digraph D which has this form is called a bisimplex in D. A biclique in D is a bisimplex in D which is not a proper subgraph of any other and in which B ≠ ∅ and C ≠ ∅. The biclique digraph C→ (D) of D is the digraph whose vertex set is the set of all bicliques in D and in which there is an arc from K(B1, C1) into K(B2, C2) if and only if C1 ∩ B2 = ∅. The operator which assigns C→ (D) to D is the biclique operator C→ . The paper solves a problem of E. Prisner concerning the periodicity of C→ .
The signed edge domination number of a graph is an edge variant of the signed domination number. The closed neighbourhood NG[e] of an edge e in a graph G is the set consisting of e and of all edges having a common end vertex with e. Let f be a mapping of the edge set E(G) of G into the set {−1, 1}. If ∑ x∈N[e] f(x) ≥ 1 for each e ∈ E(G), then f is called a signed edge dominating function on G. The minimum of the values ∑ x∈E(G) f(x), taken over all signed edge dominating function f on G, is called the signed edge domination number of G and is denoted by γ s(G). If instead of the closed neighbourhood NG[e] we use the open neighbourhood NG(e) = NG[e] − {e}, we obtain the definition of the signed edge total domination number γ st(G) of G. In this paper these concepts are studied for trees. The number γ s(T) is determined for T being a star of a path or a caterpillar. Moreover, also γ s(Cn) for a circuit of length n is determined. For a tree satisfying a certain condition the inequality γ s(T) ≥ γ (T) is stated. An existence theorem for a tree T with a given number of edges and given signed edge domination number is proved. At the end similar results are obtained for γ st(T).
The restrained domination number $\gamma ^r (G)$ and the total restrained domination number $\gamma ^r_t (G)$ of a graph $G$ were introduced recently by various authors as certain variants of the domination number $\gamma (G)$ of $(G)$. A well-known numerical invariant of a graph is the domatic number $d (G)$ which is in a certain way related (and may be called dual) to $\gamma (G)$. The paper tries to define analogous concepts also for the restrained domination and the total restrained domination and discusses the sense of such new definitions.
A caterpillar is a tree with the property that after deleting all its vertices of degree 1 a simple path is obtained. The signed 2-domination number γ 2 s (G) and the signed total 2-domination number γ 2 st(G) of a graph G are variants of the signed domination number γs(G) and the signed total domination number γst(G). Their values for caterpillars are studied.
The concept of signed domination number of an undirected graph (introduced by J. E. Dunbar, S. T. Hedetniemi, M. A. Henning and P. J. Slater) is transferred to directed graphs. Exact values are found for particular types of tournaments. It is proved that for digraphs with a directed Hamiltonian cycle the signed domination number may be arbitrarily small.
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(v)$ is its oper neighbourhood, i.e. the set of all vertices adjacent to $v$ in $G$. A mapping $f: V(G) \rightarrow \lbrace -1, 1\rbrace $, where $V(G)$ is the vertex set of $G$, is called a signed total dominating function (STDF) on $G$, if $\sum _{x \in N(v)} f(x) \ge 1$ for each $v \in V(G)$. The minimum of values $\sum _{x \in V(G)} f(x)$, taken over all STDF’s of $G$, is called the signed total domination number of $G$ and denoted by $\gamma _{\mathrm st}(G)$. A theorem stating lower bounds for $\gamma _{\mathrm st}(G)$ is stated for the case of regular graphs. The values of this number are found for complete graphs, circuits, complete bipartite graphs and graphs on $n$-side prisms. At the end it is proved that $\gamma _{\mathrm st}(G)$ is not bounded from below in general.
E. Prisner in his book Graph Dynamics defines the k-path-step operator on the class of finite graphs. The k-path-step operator (for a positive integer k) is the operator S' k which to every finite graph G assigns the graph S' k(G) which has the same vertex set as G and in which two vertices are adjacent if and only if there exists a path of length k in G connecting them. In the paper the trees and the unicyclic graphs fixed in the operator S' 3 are studied.