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.

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.