In this article, we give new lower bounds for the size of edge chromatic critical graphs with maximum degrees of \(8\) and \(9\), respectively. Furthermore, it implies that if \(G\) is a graph embeddable in a surface \(S\) with characteristics \(c(S) = -1\) or \(-2\), then \(G\) is class one if maximum degree \(\Delta \geq 8\) or \(9\), respectively.

While powers of the adjacency matrix of a finite graph reveal information about walks on the graph, they fail to distinguish closed walks from cycles. Using elements of an appropriate commutative, nilpotent-generated algebra, a “new” adjacency matrix \(\Lambda\) can be associated with a random graph on \(n\) vertices. Letting \(X_k\) denote the number of \(k\)-cycles occurring in a random graph, this algebra together with a probability mapping allow \(\mathbb{E}(X_k)\) to be recovered in terms of \(\operatorname{tr} \Lambda^k\). Higher moments of \(X_k\) can also be computed, and conditions are given for the existence of higher moments in growing sequences of random graphs by considering infinite-dimensional algebras. The algebras used can be embedded in algebras of fermion creation and annihilation operators, thereby establishing connections with quantum computing and quantum probability theory. In the framework of quantum probability, the nilpotent adjacency matrix of a finite graph is a quantum random variable whose \(m\)th moment corresponds to the \(m\)-cycles contained in the graph.

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