In this paper, we count the number of isomorphism classes of bipartite \(n\)-cyclic permutation graphs up to positive natural isomorphism and show that it is equal to the number of double cosets of the dihedral group \(D_n\) in the subgroup \(B_n\) of the symmetric group \(S_n\), consisting of parity-preserving or parity-reversing permutations.

Let \(\alpha(G)\) denote the independence number of a graph \(G\) and let \(G \times H\) be the direct product of graphs \(G\) and \(H\). Set \(\underline{\alpha}(G\times H) = \max\{\alpha(G) – |H|, \alpha(H) – |G|\}\). If \(G\) is a path or a cycle and \(H\) is a path or a cycle, then \(\alpha(G \times H) = \underline{\alpha}(G \times H)\). Moreover, this equality holds also in the case when \(G\) is a bipartite graph with a perfect matching and \(H\) is a traceable graph. However, for any graph \(G\) with at least one edge and for any \(i \in \mathbb{N}\), there is a graph \(H_c\) such that \(\alpha(G \times H ) > \underline{\alpha}(G \times H ) + i\).

Our main aim is to show that the Randi\’e weight of a connected graph of order \(n\) is at least \(\sqrt{n – 1}\). As shown by the stars, this bound is best possible.

New class \(\mathcal{GBG}_{\overrightarrow{k}}\), of generalized de Bruijn multigraphs of rank \({\overrightarrow{k}}\in{N}^m\), is introduced and briefly characterized. It is shown, among the others, that every multigraph of \(\mathcal{GBG}_{\overrightarrow{k}}\) is connected, Eulerian and Hamiltonian. Moreover, it consists of the subgraphs which are isomorphic with the de Bruijn graphs of rank \(r=\sum_{i=1}^{m} (d_1,\dots,d_m)\in\{0.1\}^m\). Then, the subgraphs of every multigraph of \(\mathcal{GBG}_{\overrightarrow{k}}\), called the \({\overrightarrow{k}}\)-factors, are distinguished.

An algorithm, with small time and space complexities, for the construction of the \({\overrightarrow{k}}\)-factors, in particular the Hamiltonian circuits, is given. At the very end, a few open problems are put forward.

A graph \(G\) is collapsible if for every even subset \(R \subseteq V(G)\), there is a spanning connected subgraph of \(G\) whose set of odd degree vertices is \(R\). A graph is supereulerian if it contains a spanning closed trail. It is known that every collapsible graph is supereulerian. A graph \(G\) of order \(n\) is said to satisfy a Fan-type condition if \(\max\{d(u),d(v)\} \geq \frac{n}{(g-2)p} – \epsilon\) for each pair of vertices \(u,v\) at distance two, where \(g \in \{3,4\}\) is the girth of \(G\), and \(p \geq 2\) and \(\epsilon \geq 0\) are fixed numbers. In this paper, we study the Fan-type conditions for collapsible graphs and supereulerian graphs.

Let \(n \geq 1\) be an integer. The closed \(n\)-neighborhood \(N_n[u]\) of a vertex \(u\) in a graph \(G = (V, E)\) is the set of vertices \(\{v | d(u,v) \leq n\}\). The closed \(n\)-neighborhood of a set \(X\) of vertices, denoted by \(N_n[X]\), is the union of the closed \(n\)-neighborhoods \(N_n[v]\) of vertices \(u \in X\). For \(X \subseteq V(G)\), if \(N_n[x] – N_n[X – \{u\}] = \emptyset\), then \(u\) is said to be \(n\)-redundant in \(X\). A set \(X\) containing no \(n\)-redundant vertex is called \(n\)-irredundant. The \(n\)-irredundance number of \(G\), denoted by \(ir_n(G)\), is the minimum cardinality taken over all maximal \(n\)-irredundant sets of vertices of \(G\). The upper \(n\)-irredundance number of \(G\), denoted by \(IR_n(G)\), is the maximum cardinality taken over all maximal \(n\)-irredundant sets of vertices of \(G\). In this paper we show that the decision problem corresponding to the computation of \(ir_n(G)\) for bipartite graphs \(G\) is NP-complete. We then prove that this also holds for augmented split graphs. These results extend those of Hedetniemi, Laskar, and Pfaff (see [7]) and Laskar and Pfaff (see [8]) for the case \(n = 1\). Lastly, applying the general method described by Bern, Lawler, and Wong (see [1]), we present linear algorithms to compute the \(2\)-irredundance and upper \(2\)-irredundance numbers for trees.

Some properties of finite projective planes are used to obtain some new pairwise balanced designs with consecutive block sizes, by deleting configurations spanned by lines.

We give a short survey of the best known lower bounds on \(K(n, 1)\), the minimum cardinality of a binary code of length \(n\) and covering radius \(1\). Then we prove new lower bounds on \(K(n, 1)\), e.g.
\[K(n,1)\geq \frac{(5n^2-13n+66)2^n}{(5n^2-13n+46)(n+1)}\] when \(n \equiv 5 \pmod{6}\)
which lead to several numerical improvements.

In this paper, we study path-factors and path coverings of a claw-free graph and those of its closure. For a claw-free graph \(G\) and its closure \( cl(G)\), we prove:(1) \(G\) has a path-factor with \(r\) components if and only if \( cl(G)\) has a path-factor with \(r\) components,(2) \(V(G)\) is covered by \(k\) paths in \(G\) if and only if \(V( cl(G))\) is covered by \(k\) paths in \( cl(G)\).

Let \(G = (V,E)\) be a connected graph. Let \(\gamma_c(G), d_c(G)\) denote the connected domination number, connected domatic number of \(G\), respectively. We prove that \(\gamma_c(G) \leq 3d_c(G^c)\) if the complement of \(G\) is also connected. This confirms a conjecture of Hedetniemi and Laskar (1984), and Sun (1992). Examples are given to show that equality may occur.