In \([2]\) it was introduced the concept of the kernel by monochromatic paths, which generalize concept of kernel. In this paper we prove the necessary and sufficient conditions for the existence of kernels by monochromatic paths in the \(D\)-join of digraphs. We also give sufficient condition for \(D\)-join to be monochromatic kernel perfect. The existence of generalized kernel (in distance sense) in D-join were studied in \([5]\). Moreover we calculate the total number of kernels by monochromatic paths in this product.

For integers \(p, q, s\) with \(p \geq q \geq 3\) and \(1 \leq s \leq q-1\), let \(\mathcal{K}^{-s}{p,q}\) (resp. \(\mathcal{K}_2^{-s}{p,q}\)) denote the set of connected (resp. 2-connected) bipartite graphs which can be obtained from \(K_{p,q}\) by deleting a set of \(s\) edges. In this paper, we prove that for any \(G \in \mathcal{K}_2^{-s}{p,q}\) with \(p \geq q \geq 3\), if \(9 \leq s \leq q-1\) and \(\Delta(G’) = s-3\) where \(G’ = K_{p,q} – G\), then \(G\) is chromatically unique.

Let \(k\) be a positive integer and \(G\) a graph with order \(n \geq 4k + 3\). It is proved that if the minimum degree sum of any two nonadjacent vertices is at least \(n + k\), then \(G\) contains a 2-factor with \(k + 1\) disjoint cycles \(C_1, \ldots, C_{k+1}\) such that \(C_i\) are chorded quadrilaterals for \(1 \leq i \leq k-1\) and the length of \(C_{k}\) is at most \(4\).

A finite simple graph is of class one if its edge chromatic number is equal to the maximum degree of this graph. It is proved here that every planar graph with the maximum degree \(5\) and without \(4\) or \(5\)-cycles is of class one. One of Zhou’s results is improved.

A cycle \(C\) in a graph \(G\) is said to be dominating if \(E(G-C) = 0\). Enomoto et al. showed that if \(G\) is a 2-connected triangle-free graph with \(\alpha(G) \leq 2\kappa(G) – 2\), then every longest cycle is dominating. But it is unknown whether the condition on the independence number is sharp. In this paper, we show that if \(G\) is a 2-connected triangle-free graph with \(\alpha(G) \leq 2\kappa(G) – 1\), then \(G\) has a longest cycle which is dominating. This condition is best possible.

In this paper, we obtain the explicit recurrences of the independence polynomials of polygonal cactus chains of two classes, and show that they are the extremal polygonal cactus chains with respect to the number of independent sets.

We prove that the power of cycles \(C_n^2\) for odd \(n\) are antimagic. We provide explicit constructions to demonstrate that all powers of cycles \(C_n^2\) for odd \(n\) are antimagic and their vertex sums form a set of successive integers.

A graph \(G = (V, E)\) is Skolem-graceful if its vertices can be labelled \(1, 2, \ldots, |V|\), so that the edges are labelled \(1, 2, \ldots, |E|\), where each edge label is the absolute difference of the labels of the two end-vertices. It is shown that a \(k\)-star is Skolem-graceful only if at least one star has even size or \(k \equiv 0\) or \(1 \pmod{4}\), and for \(k \leq 5\), a \(k\)-star is Skolem-graceful if at least one star has even size or \(k \equiv 0\) or \(1 \pmod{4}\). In this paper, we show that \(k\)-stars are Skolem-graceful if at least one star has even size or \(k \equiv 0\) or \(1 \pmod{4}\) for all positive integer \(k\).

Let \(\Gamma\) be a \(d\)-bounded distance-regular graph with diameter \(d \geq 3\) and with geometric parameters \((d, b, \alpha)\). Pick \(x \in V(\Gamma)\), and let \(P(x)\) be the set of all subspaces containing \(x\). Suppose \(P(x, m)\) is the set of all subspaces in \(P(x)\) with diameter \(m\), where \(1 \leq m < d\). Define a graph \(\Gamma'\) whose vertex-set is \(P(x, m)\), and in which \(\Delta_1\) is adjacent to \(\Delta_2\) if and only if \(d(\Delta_1 \cap \Delta_2) = m – 1\). We prove that \(\Gamma'\) is a distance-regular graph and compute its intersection numbers.

Let \(G\) be a \(contraction-critical\) \(\kappa\)-connected graph. It is known (see Graphs and Combinatorics, \(7 (1991) 15-21\)) that the minimum degree of \(G\) is at most \(\lfloor \frac{5\kappa}{4} \rfloor – 1\). In this paper, we show that if \(G\) has at most one vertex of degree \(\kappa\), then either \(G\) has a pair of adjacent vertices such that each of them has degree at most \(\lfloor \frac{5\kappa}{4} \rfloor – 1\), or there is a vertex of degree \(\kappa\) whose neighborhood has a vertex of degree at most \(\lfloor \frac{4\kappa}{4} \rfloor – 1\). Moreover, if the minimum degree of \(G\) equals to \(\frac{5\kappa}{4} – 1\) (and thus \(\kappa = 0 \mod 4\)), Su showed that \(G\) has \(\kappa\) vertices of degree \(\frac{5\kappa}{4} – 1\), guessed that \(G\) has \(\frac{3\kappa}{2}\) such vertices (see Combinatorics Graph Theory Algorithms and Application (Yousef Alavi et. al Eds.),World Scientific, \(1993, 329-337\)). Here, we verify that this is true.