Crossing numbers of graphs are in general very difficult to compute. There are several known exact results on the crossing numbers of Cartesian products of paths, cycles or stars with small graphs. In this paper we study \(\text{cr}(W_{1,m} \Box P_{n})\), the crossing number of Cartesian product \(W_{l,m} \Box P_{n}\), where \(W_{l,m}\) is the cone graph \(C_{m} + \overline{K_{l}}\). Klešč showed that \(\text{cr}(W_{1,3} \Box P_{n}) = 2n\) (Journal of Graph Theory, \(6(1994), 605-614)\)), \(\text{cr}(W_{1,4} \Box P_{n}) = 3n – 1\) and \(\text{cr}(W_{2,3} \Box P_{n}) = 4n\) (Discrete Mathematics, \(233(2001),353-359\)). Huang \(et\) \(al\). showed that \(\text{cr}(W_{1,m} \Box P_{n}) = (n – 1)\lfloor\frac{m}{2}\rfloor \lfloor\frac{m-1}{2}\rfloor +n+1\). for \(n \leq 3\) (Journal of Natural Science of Hunan Normal University,\(28(2005), 14-16)\). We extend these results and prove \(\text{cr}(W_{1,m} \Box P_{n}) = (n – 1) \left\lfloor \frac{m}{2} \right\rfloor\lfloor \frac{m-1}{2}\rfloor + n+1\) and \(\text{cr}(W_{2,m} \Box P_{n}) = 2n \left\lfloor \frac{m}{2} \right\rfloor\lfloor\frac{m-1}{2} \rfloor + 2n\).

A double-loop network (DLN) \(G(N;1,s)\) with \(1 < s < N\), is a digraph with the vertex set \(V = \{0,1,\ldots,N – 1\}\) and the edge set \(E=\{u\to v\mid v-u\equiv 1,s \pmod{N}, u,v \in V\}\). Let \(D(N;1,s)\) be the diameter of \(G\) and let us define \(D(N) = \min\{D(N;1,s)\mid 1 < s < N\}\) and \(lb(N) = \lceil\sqrt{3N}\rceil – 2\). A given DLN \(G(N;1,s)\) is called \(k\)-tight if \(D(N;1,s) = lb(N) + k\) (\(k \geq 0\)). A \(k\)-tight DLN is called optimal if \(D(N) = lb(N) + k\) (\(k \geq 0\)). It is known that finding \(k\)-tight optimal DLN is a difficult task as the value \(k\) increases. In this work, a practical algorithm is derived for finding \(k\)-tight optimal double-loop networks (\(k \geq 0\)), and it is proved that the average complexity to judge whether there exists a \(k\)-tight \(L\)-shaped tile with \(N\) nodes is \(O(k^2)\). As application examples, we give some \(9\)-tight optimal DLN and their infinite families.

Let \(k\) be a positive integer and let \(G = (V(G), E(G))\) be a graph with \(|V(G)| \geq 4k\). In this paper, it is proved that if the minimum degree sum is at least \(6k – 1\) for each pair of nonadjacent vertices in \(V(G)\), then \(G\) contains \(k\) vertex-disjoint chorded cycles. This result generalizes the main Theorem of Finkel. Moreover, the degree condition is sharp in general.

Let \(G = (V, E)\) be a finite simple connected graph. For any vertex \(v\) in \(V\), let \(N_G(v) = \{u \in V: uv \in E\}\) be the open neighbourhood of \(v\), and let \(N_G[v] = N_G(v) \cup \{v\}\) be the closed neighbourhood of \(v\). A connected graph \(G\) is said to be neighbourhood highly irregular (or simply NHI) if for any vertex \(v \in V\), any two distinct vertices in the open neighbourhood of \(v\) have distinct closed neighbourhood sets. In this paper, we give a necessary and sufficient condition for a graph to be NHI. For any \(n \geq 1\), we obtain a lower bound for the order of regular NHI graphs and a sharp lower bound for the order of NHI graphs with clique number \(n\), which is better than the bound attained earlier.

In this paper, we initiate the study of \(k\)-connected restrained domination in graphs. Let \(G = (V,E)\) be a graph. A \(k\)-connected restrained dominating set is a set \(S \subseteq V\) where \(S\) is a restrained dominating set and \(G[S]\) has at most \(k\) components. The \(k\)-connected restrained domination number of \(G\), denoted by \(\gamma_r^k(G)\), is the smallest cardinality of a \(k\)-connected restrained dominating set of \(G\). First, some exact values and sharp bounds for \(\gamma_r^k(G)\) are given in Section 2. Then, the necessary and sufficient conditions for \(\gamma_r(G) = \gamma_r^1(G) = \gamma_r^2(G)\) are given if \(G\) is a tree or a unicyclic graph in Section 3 and Section 4.

The first two authors have shown, in \([13]\), that if \(K_{r,r} \times K_{m}\), \(m \geq 3\), is an even regular graph, then it is Hamilton cycle decomposable, where \(\times\) denotes the tensor product of graphs. In this paper, it is shown that if \((K_{r,r} \times K_{m})^*\) is odd regular, then \((K_{r,r} \times K_{m})^*\) is directed Hamilton cycle decomposable, where \((K_{r,r} \times K_{m})^*\) denotes the symmetric digraph of \(K_{r,r} \times K_{m}\).

In \([8]\) the concept of \(H\)-kernel was introduced, which generalizes the concepts of kernel and kernel by monochromatic paths. In this paper, we prove necessary and sufficient conditions for the existence of H-kernels in the \(D\)-join of digraphs, and consequently, we will give a sufficient condition for the \(D\)-join to be \(H\)-kernel perfect.

Let \(\operatorname{MPT}(v,\lambda)\) denote a maximum packing of triples of order \(v\) with index \(\lambda\). For \(\lambda > 1\) and \(v \geq 3\), it is proved in this paper that the necessary and sufficient condition for the embedding of an \(\operatorname{MPT}(v,\lambda)\) in an \(\operatorname{MPT}(u,\lambda)\) is \(u \geq 20v + 1\).

The maximal and next-to-maximal subspaces of a nonsingular parabolic quadric \(Q(2n,2)\), \(n \geq 2\), which are not contained in a given hyperbolic quadric \(Q_+(2n-1,q) \subset Q(2n,q)\) define a sub near polygon \(\mathbb{I}_n\) of the dual polar space \(DQ(2n,2)\). It is known that every valuation of \(DQ(2n,2)\) induces a valuation of \(\mathbb{I}_n\). In this paper, we show that also the converse is true: every valuation of \(\mathbb{I}_n\) is induced by a valuation of \(DQ(2n,2)\). We will also study the structure of the valuations of \(\mathbb{I}_n\).

The (Laplacian) spectral radius of a graph is the maximum eigenvalue of its adjacency matrix (Laplacian matrix, respectively). Let \(\mathcal{G}(n,k)\) be the set of bipartite graphs with \(n\) vertices and \(k\) blocks. This paper gives a complete characterization for the extremal graph with the maximum spectral radius (Laplacian spectral radius, respectively) in \(\mathcal{G}(n, k)\).