A set \(S = \{v_1, v_2, \ldots, v_n\}\) of vertices in a graph \(G\) with associated sequence \(k_1, k_2, \ldots, k_n\) of nonnegative integers is called a step domination set if every vertex of \(G\) is at distance \(k_i\) from \(v_i\) for exactly one \(i\) (\(1 \leq i \leq n\)). The minimum cardinality of a step domination set is called the step domination number of \(G\). This parameter is determined for several classes of graphs and is investigated for trees.

We completely determine the spectrum (i.e. set of orders) of complete \(4\)-partite graphs with at most one odd part which are decomposable into two isomorphic factors with a finite diameter. For complete \(4\)-partite graphs with all parts odd we solve the spectrum problem completely for factors with diameter \(5\). As regards the remaining possible finite diameters, \(2, 3, 4\), we present partial results, focusing on decompositions of \(K_{n,n,n,m}\) and \(K_{n,n,m,m}\) for odd \(m\) and \(n\).

In this paper we determine the \(k\)-domination numbers of the cardinal products \(P_2 \times P_n, \ldots, P_{2k+1} \times P_n\) for all integers \(k \geq 2, n \geq 3\).

In this paper we investigate the nature of both the \(2\)-packing number and the minimum domination number of the cartesian product of graphs where at least one of them has the property that every vertex is either a leaf or has at least one leaf as a neighbour.

Let \(H\) be a graph, and let \(k\) be a positive integer. A graph \(G\) is \(H\)-coverable with overlap \(k\) if there is a covering of all the edges of \(G\) by copies of \(H\) such that no edge of \(G\) is covered more than \(k\) times. The number \(ol(H, G)\) is the minimum \(k\) for which \(G\) is \(H\)-coverable with overlap \(k\).

It is established (Theorem 2.1) that if \(n\) is sufficiently large then
\[ol(H, K_n) \leq 2.\]

For \(H\) being a path, a matching or a star it is enough to assume \(|H| \leq n\) (Theorem 3.1).

The same result is obtained (Main Theorem) for any graph \(H\) having at most four vertices, or else at most four edges with a single exception \(ol(K_4, K_5) = 3\).

Given a digraph (an undirected graph, resp.) \(D\) and two positive integers \(f(x), g(x)\) for every \(x \in V(D)\), a subgraph \(H\) of \(D\) is called a \((g, f)\)-factor if \(g(x) \leq d^+_H(x) = d^-_H(x) \leq f(x)\) (\(g(x) \leq d_H(x) \leq f(x)\), resp.) for every \(x \in V(D)\). If \(f(x) = g(x) = 1\) for every \(x\), then a connected \((g, f)\)-factor is a hamiltonian cycle. The previous research related to the topic has been carried out either for \((g, f)\)-factors (in general, disconnected) or for hamiltonian cycles separately, even though numerous similarities between them have been recently detected. Here we consider connected \((g, f)\)-factors in digraphs and show that several results on hamiltonian digraphs, which are generalizations of tournaments, can be extended to connected \((g, f)\)-factors. Applications of these results to supereulerian digraphs are also obtained.

Let \(G\) be a group of permutations acting on an \(7\)-vertex set \(V\), and \(X\) and \(Y\) be two simple graphs on \(V\). We say that \(X\) and \(Y\) are \(G\)-isomorphic if \(Y\) belongs to the orbit of \(X\) under the action of \(G\). One can naturally generalize the reconstruction problems so that when \(G\) is \(S_v\), the symmetric group, we have the usual reconstruction problems. In this paper, we study \(G\)-edge reconstructibility of graphs. We prove some old and new results on edge reconstruction and reconstruction from end vertex deleted subgraphs.

Frucht and Salinas [1] conjectured that \(C(k) \cup P(n)\) (\(n \geq 3\)) is graceful if and only if \(k + n \geq 7\). We prove that \(C(2k) \cup P(n)\) is graceful for \(n > k + 1\) (\(k \geq 3\)).

For smaller cases we prove that \(C(2k) \cup P(n)\) is graceful for \(k = 3, 4, 5, 6; n \geq 2\).

We present necessary and sufficient conditions for the decomposition of the complete symmetric bipartite digraph into each of the orientations of a \(4\)-cycle (in the cases for which such decompositions are not already known). We use these results to find optimal packings of the complete symmetric digraph with each of the orientations of a \(4\)-cycle. Finally, we give necessary and sufficient conditions for the existence of a decomposition of the complete symmetric digraph on \(v\) vertices with a hole of size \(w\) into each of the orientations of a \(4\)-cycle.