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)\).

In the paper “A note on the eigenvalues of graphs, Ars Combinatoria \(94 (2010), 221-227\)” by Lihua Feng and Guihai Yu, page 226, we have the following note.

In this paper, we show that among all connected graphs of order \(n\) with diameter \(D\), the graph \(G^*\) has maximal spectral radius, where \(G^*\) is obtained from \(K_{n-D} \bigvee \overline{K_2}\) by attaching two paths of order \(l_1\) and \(l_2\) to the two vertices \(u,v\) in \(\overline{K_2}\), respectively, and \(l_1 + l_2 = D-2\), \(|l_1 – l_2| \leq 1\).

P. Erdés and T. Gallai gave necessary and sufficient conditions for a sequence of non-negative integers to be graphic. Here,their result is generalized to multigraphs with a specified multiplicity. This both generalizes and provides a new proof of a result in the literature by Chungphaisan \([2].\)

Let \(u\) and \(v\) be two vertices in a graph \(G\). We say vertex \(u\) dominates vertex \(v\) if \(N(v) \subseteq N(u) \cup \{u\}\). If \(u\) dominates \(v\) or \(v\) dominates \(u\), then \(u\) and \(v\) are comparable. The Dilworth number of a graph \(G\), denoted \(\operatorname{Dil}(G)\), is the largest number of pairwise incomparable vertices in the graph \(G\). A graph \(G\) is called claw-free if \(G\) has no induced subgraph isomorphic to \(K_{1,3}\). It is shown that if \(G\) is a \(k\) (\(k \geq 3\)) – connected claw-free graph with \(\operatorname{Dil}(G) \leq 2k-5\), then \(G\) is Hamilton-connected and a Hamilton path between every two vertices in \(G\) can be found in polynomial time.

In this paper, we analyze the familiar straight insertion sort algorithm and quantify the deviation of the output from the correct sorted order if the outcomes of one or more comparisons are in error. The disarray in the output sequence is quantified by six measures. For input sequences whose length is large compared to the number of errors, a comparison is made between the robustness to errors of bubble sort and the robustness to errors of straight insertion sort. In addition to analyzing the behaviour of straight insertion sort, we review some inequalities among the various measures of disarray, and prove some new ones.