Graceful labellings have both a mathematical beauty in their own right and considerable connections with pure and applied combinatorics (edge-decomposition of graphs, coding systems, communication networks, etc.). In the present paper, we exhibit a graceful labelling for each generalized Petersen graph \(P_{8t,3}\) with \(t \geq 1\). As a consequence, we obtain, for any fixed \(t\), a cyclic edge-decomposition of the complete graph \(K_{48t+1}\) into copies of \(P_{8t,3}\). Due to its extreme versatility, the technique employed looks promising for finding new graceful labellings, not necessarily involving generalized Petersen graphs.

A graph on \(n\) vertices having no vertex of degree greater than \(f\), \(2 \leq f \leq n – 2\), is called an \(f\)-graph of order \(n\). For a given \(f\), the vertices of degree less than \(f\) are called orexic. An \(f\)-graph to which no edge can be added without violating the \(f\)-degree restriction is called an edge maximal \(f\)-graph (EM \(f\)-graph). An upper bound, as a function of \(n\) and \(f\), for the number of orexic vertices in an EM \(f\)-graph and the structure of the subgraph induced by its orexic vertices is given. For any \(n\) and \(f\), the maximum size, minimum size, and realizations of extremal size EM \(f\)-graphs having \(m\) orexic vertices and order \(n\) are obtained. This is also done for any given \(n\) and \(f\) independent of \(m\). The number of size classes of EM \(f\)-graphs of order \(n\) and fixed \(m\) is determined. From this, the maximum number of size classes over all \(m\) follows. These results are related to the study of \((f + 1)\)-star-saturated graphs.

We give a decomposition formula for the edge zeta function of a regular covering \(\overrightarrow{G}\) of a graph \(G\). Furthermore, we present a determinant expression for some \(Z\)-function of an oriented line graph \(\overrightarrow{L}(G)\) of \(G\). As a corollary, we obtain a factorization formula for the edge zeta function of \(\overrightarrow{G}\) by \(L\)-functions of \(\overrightarrow{L}(G)\).

A hamiltonian graph \(G\) is panpositionable if for any two different vertices \(x\) and \(y\) of \(G\) and any integer \(k\) with \(d_G(x,y) \leq k \leq |V(G)|/2\), there exists a hamiltonian cycle \(C\) of \(G\) with \(d_C(x,y) = k\). A bipartite hamiltonian graph \(G\) is bipanpositionable if for any two different vertices \(x\) and \(y\) of \(G\) and for any integer \(k\) with \(d_G(x,y) \leq k \leq |V(G)|/2\) and \((k – d_G(x,y))\) is even, there exists a hamiltonian cycle \(C\) of \(G\) such that \(d_C(x,y) = k\). In this paper, we prove that the hypercube \(Q_n\) is bipanpositionable hamiltonian if and only if \(n \geq 2\). The recursive circulant graph \(G(n;1,3)\) is bipanpositionable hamiltonian if and only if \(n \geq 6\) and \(n\) is even; \(G(n; 1,2)\) is panpositionable hamiltonian if and only if \(n \in \{5,6,7,8,9, 11\}\), and \(G(n; 1, 2,3)\) is panpositionable hamiltonian if and only if \(n \geq 5\).

The lower domination number of a digraph \(D\), denoted by \(\gamma(D)\), is the least number of vertices in a set \(S\), such that \(O[S] = V(D)\). A set \(S\) is irredundant if for all \(x \in S\), \(|O[x] – O[S – x]| \geq 1\). The lower irredundance number of a digraph, denoted \(ir(D)\), is the least number of vertices in a maximal irredundant set. A Gallai-type theorem has the form \(x(G) + y(G) = n\), where \(x\) and \(y\) are parameters defined on \(G\), and \(n\) is the number of vertices in the graph. We characterize directed trees satisfying \(\gamma(D) + \Delta_+(D) = n\) and directed trees satisfying \(ir(D) + \Delta_+(D) = n\).

We introduce a new concept of strong domination and connected strong domination in hypergraphs. The relationships between strong domination number and other hypergraph parameters like domination, independence, strong independence and irredundant numbers of hypergraphs are considered. There are also some chains of inequalities generalizing the famous Cockayne, Hedetniemi and Miller chain for parameters of graphs. There are given some generalizations of well known theorems for graphs, namely Gallai type theorem generalizing Nieminen, Hedetniemi and Laskar theorems.

The vertex linear arboricity \(vla(G)\) of a graph \(G\) is the minimum number of subsets into which the vertex set \(V(G)\) can be partitioned so that each subset induces a subgraph whose connected components are paths. In this paper, we seek to convert vertex linear arboricity into its fractional analogues, i.e., the fractional vertex linear arboricity of graphs. Let \(\mathbb{Z}_n\) denote the additive group of integers modulo \(n\). Suppose that \(C \subseteq \mathbb{Z}_n \backslash 0\) has the additional property that it is closed under additive inverse, that is, \(-c \in C\) if and only if \(c \in C\). A circulant graph is the graph \(G(\mathbb{Z}_n, C)\) with the vertex set \(\mathbb{Z}_n\) and \(i, j\) are adjacent if and only if \(i – j \in C\). The fractional vertex linear arboricity of the complete \(n\)-partite graph, the cycle \(C_n\), the integer distance graph \(G(D)\) for \(D = \{1, 2, \ldots, m\}\), \(D = \{2, 3, \ldots, m\}\) and \(D = P\) the set of all prime numbers, the Petersen graph and the circulant graph \(G(\mathbb{Z}_a, C)\) with \(C = \{-a + b, \ldots, -b, b, \ldots, a – b\}\) (\(a – 2b \geq b – 3 \geq 3\)) are determined, and an upper and a lower bounds of the fractional vertex linear arboricity of Mycielski graph are obtained.

Deciding whether a graph can be partitioned into \(k\) vertex-disjoint paths is a well-known NP-complete problem. In this paper, we give new sufficient conditions for a bipartite graph to be partitionable into \(k\) vertex-disjoint paths. We prove the following results for a simple bipartite graph \(G = (V_1, V_2, E)\) of order \(n\):(i) For any positive integer \(k\), if \(\|V_1| – |V_2\| \leq k\) and \(d_G(x) + d_G(y) \geq \frac{n-k+1}{2}\) for every pair \(x \in V_1\) and \(y \in V_2\) of nonadjacent vertices of \(G\), then \(G\) can be partitioned into \(k\) vertex-disjoint paths, unless \(k = 1\), \(|V_1| = |V_2| = \frac{n}{2}\) and \(G = K_{s,s} \cup K_{\frac{n}{2} – s, \frac{n}{2} – s} \cup K_{2, 2}\), where \(1 \leq k \leq \frac{n}{2} – 1\);(ii) For any two positive integers \(p_1\) and \(p_2\) satisfying \(n = p_1 + p_2\), if \(G\) does not belong to some easily recognizable classes of exceptional graphs, \(\|V_1| – |V_2\| \leq 2\) and \(d_G(x) + d_G(y) = \frac{n-1}{2}\) for every pair \(x \in V_1\) and \(y \in V_2\) of nonadjacent vertices of \(G\), then \(G\) can be partitioned into two vertex-disjoint paths \(P_{1}\) and \(P_{2}\) of order \(p_1\) and \(p_2\), respectively.These results also lead to new sufficient conditions for the existence of a Hamilton path in a bipartite graph.

In this paper we compute the chirality group, the chirality index and the smallest regular coverings of the chiral Coxeter maps, the toroidal orientably regular maps described in Coxeter and Moser monograph [H.S.M.Coxeter and W.O.J.Moser,Generation and Relations Discrete Group(4th ed.),Springer-varlag,Berlin,1984]. We also compute the greatest regular maps covered by chiral Coxeter maps.

We observe that a lobster with diameter at least five has a unique path \(x_0, x_1, \ldots, x_{m}\) (called the central path) such that \(x_p\) and \(x_m\) are adjacent to the centers of at least one \(K_{1,s}\), \(s > 0\), and besides adjacencies in the central path each \(x_i\), \(1 \leq i \leq m-1\), is at most adjacent to the centers of some \(K_{1,s}\), \(s \geq 0\). In this paper we give graceful labelings to some new classes of lobsters with diameter at least five, in which the degree of the vertex \(x_m\) is odd and the degree of each of the remaining vertices on the central path is even. The main idea used to obtain these graceful lobsters is to form a diameter four tree \(T(L)\) from a lobster \(L\) of certain type, give a graceful labeling to \(T(L)\) and finally get a graceful labeling of \(L\) by applying component moving and inverse transformations.