Let \(G\) be a graph of order \(n\). In [A. Saito, Degree sums and graphs that are not covered by two cycles, J. Graph Theory 32 (1999), 51–61.], Saito characterized the graphs with \(\sigma_3(G) \geq n-1\) that are not covered by two cycles. In this paper, we characterize the graphs with \(\sigma_4(G) \geq n-1\) that are not covered by three cycles. Moreover, to prove our main theorem, we show several new results which are useful in the study of this area.

Let \(\mathcal{B}(n, a)\) be the set of bicyclic graphs on \(n\) vertices with matching number \(\alpha\). In this paper, we characterize the extremal bicyclic graph with minimal Hosoya index and maximal Merrifield-Simmons index in \(\mathcal{B}(n, a)\).

A word has a shape determined by its image under the Robinson-Schensted-Knuth correspondence. We show that when a word \(w\) contains a separable (i.e., \(3142\)- and \(2413\)-avoiding) permutation \(\sigma\) as a pattern, the shape of \(w\) contains the shape of \(\sigma\). As an application, we exhibit lower bounds for the lengths of supersequences of sets containing separable permutations.

Two graphs are defined to be adjointly equivalent if their complements are chromatically equivalent. In \([2, 7]\), Liu and Dong et al. give the first four coefficients \(b_0\), \(b_1\), \(b_2\), \(b_3\) of the adjoint polynomial and two invariants \(R_1\), \(R_2\), which are useful in determining the chromaticity of graphs. In this paper, we give the expression of the fifth coefficient \(b_4\), which brings about a new invariant \(R_3\). Using these new tools and the properties of the adjoint polynomials, we determine the chromatic equivalence class of \(\overline{B_{n-9,1,5}}\).

Given a tournament \(T = (V, A)\), a subset \(X\) of \(V\) is an interval of \(T\) provided that for any \(a, b \in X\) and \(x \in V – X\), \((a, x) \in A\) if and only if \((b, x) \in A\). For example, \(\emptyset\), \(\{x\}\) (\(x \in V\)), and \(V\) are intervals of \(T\), called trivial intervals. A tournament whose intervals are trivial is indecomposable; otherwise, it is decomposable. With each indecomposable tournament \(T\), we associate its indecomposability graph \(\mathbb{I}(T)\) defined as follows: the vertices of \(\mathbb{I}(T)\) are those of \(T\) and its edges are the unordered pairs of distinct vertices \(\{x, y\}\) such that \(T -\{x, y\}\) is indecomposable. We characterize the indecomposable tournaments \(T\) whose \(\mathbb{I}(T)\) admits a vertex cover of size \(2\).

Let \(G\) be a simple graph. A harmonious coloring of \(G\) is a proper vertex coloring such that each pair of colors appears together on at most one edge. The harmonious chromatic number \(h(G)\) is the least number of colors in such a coloring. In this paper, it is shown that if \(T\) is a tree of order \(n\) and \(\Delta(T) \geq \frac{n}{2}\), then \(h(T) = \Delta(T) + 1\), where \(\Delta(T)\) denotes the maximum degree of \(T\). Let \(T_1\) and \(T_2\) be two trees of order \(n_1\) and \(n_2\), respectively, and \(F = T_1 \cup T_2\). In this paper, it is shown that if \(\Delta(T_i) = \Delta_i\) and \(\Delta_i \geq \frac{n_i}{2}\), for \(i = 1, 2\), then \(h(F) \leq \Delta(F) + 2\). Moreover, if \(\Delta_1 = \Delta_2 = \Delta \geq \frac{n_i}{2}\), for \(i = 1, 2\), then \(h(F) = \Delta + 2\).