A vertex \(v \in V(G)\) is said to be a self vertex switching of \(G\) if \(G\) is isomorphic to \(G^v\), where \(G^v\) is the graph obtained from \(G\) by deleting all edges of \(G\) incident to \(v\) and adding all edges incident to \(v\) which are not in \(G\). In [6], the author characterized connected unicyclic graphs each with a self vertex switching. In this paper, we characterize disconnected unicyclic graphs each with a self vertex switching.

An \(f\)-coloring of a graph \(G\) is an edge-coloring of \(G\) such that each color appears at each vertex \(v \in V(G)\) at most \(f(v)\) times. A multi-wheel graph is a graph obtained from \(s\) cycles \(C_{n_1}, C_{n_2}, \ldots, C_{n_s}\) (\(s \geq 1\)) by adding a new vertex, say \(w\), and edges joining \(w\) to all the vertices of the \(s\) cycles. In this article, we solve a conjecture posed by Yu et al. in 2006 and prove that it is not always true. Furthermore, the classification problem of multi-wheel graphs on \(f\)-colorings is solved completely.

For a connected graph \(G = (V, E)\) of order at least two, a chord of a path \(P\) is an edge joining two non-adjacent vertices of \(P\). A path \(P\) is called a monophonic path if it is a chordless path. A longest \(x\)-\(y\) monophonic path is called an \(x\)-\(y\) detour monophonic path. A set \(S\) of vertices of \(G\) is a detour monophonic set of \(G\) if each vertex \(v\) of \(G\) lies on an \(x\)-\(y\) detour monophonic path for some \(x\) and \(y\) in \(S\). The minimum cardinality of a detour monophonic set of \(G\) is the detour monophonic number of \(G\) and is denoted by \(dm(G)\). For any two vertices \(u\) and \(v\) in \(G\), the monophonic distance \(dm(u,v)\) from \(u\) to \(v\) is defined as the length of a \(u\)-\(v\) detour monophonic path in \(G\). The monophonic eccentricity \(em(v)\) of a vertex \(v\) in \(G\) is the maximum monophonic distance from \(v\) to a vertex of \(G\). The monophonic radius \(rad_{m}(G)\) of \(G\) is the minimum monophonic eccentricity among the vertices of \(G\), while the monophonic diameter \(diam_{m}(G)\) of \(G\) is the maximum monophonic eccentricity among the vertices of \(G\). It is shown that for positive integers \(r\), \(d\), and \(n \geq 4\) with \(r < d\), there exists a connected graph \(G\) with \(rad_{m}(G) = r\), \(diam_{m}(G) = d\), and \(dm(G) = n\). Also, if \(p\), \(d\), and \(n\) are integers with \(2 \leq n \leq p-d+4\) and \(d \geq 3\), there is a connected graph \(G\) of order \(p\), monophonic diameter \(d\), and detour monophonic number \(n\). Further, we study how the detour monophonic number of a graph is affected by adding some pendant edges to the graph.

In this paper we introduce a new kind of two-parameters generalization of Pell numbers. We give two distinct graph interpretations and prove some identities for these numbers. Moreover we define matrix generators and derive the generalized Cassini formula for the introduced numbers.

A graph is said to be a neighbourly irregular graph (or simply an NI graph) if no two adjacent vertices have the same degree. In this paper, we introduce the neighbourly regular strength of a graph. Let \(G\) be a simple graph of order \(n\). Let \(NI(G)\) denote the set of all NI graphs in which \(G\) is an induced subgraph. The neighbourly regular strength of \(G\) is denoted by \(NRS(G)\) and is defined as the minimum \(k\) for which there is an NI graph \(NI(G)\) of order \(n+k\) in \(NI(G)\). We prove that the \(NRS(G)\) is at most \(n-1\), with possible equality only if \(G\) is complete. In addition, we determine the \(NRS\) for some well-known graphs.

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