The Merrifield-Simmons index \(i(G)\) of a graph \(G\) is defined as the total number of independent sets of \(G\). A connected graph \(G = (V,E)\) is called a quasi-unicyclic graph if there exists a vertex \(u_0 \in V\) such that \(G – u_0\) is a unicyclic graph. Denote by \(\mathcal{U}(n,d_0)\) the set of quasi-unicyclic graphs of order \(n\) with \(G – u_0\) being a unicyclic graph and \(d_G(u_0) = d_0\). In this paper, we characterize the quasi-unicyclic graphs with the smallest, the second-smallest, the largest, and the second-largest Merrifield-Simmons indices, respectively, in \(\mathcal{U}(n, d_0)\).

A unicyclic map is a rooted planar map such that there is only one cycle which is the boundary of the unique inner face (the inner face contains no trees) and the root-vertex is on the cycle. In this paper we investigate the number of unicyclic maps and present some formulae for such maps with up to three parameters: the number of edges and the valencies of the root-vertex and the root-face.

Brualdi and Massey in \(1993\) posed two conjectures regarding the upper bound for incidence coloring number of graphs in terms of maximum degree. In this paper among some results, we prove these conjectures for some classes of graphs with maximum degree \(4\).

P. Erdős, F. Harary, and M. Klawe studied the \(K_n\)-residual graph and came up with some conjectures and conclusions about the \(m-K_n\)-residual graph. For connected \(m-K_2\)-residual graphs, they constructed an \(m-K_2\)-residual graph of order \(3m+2\) and proposed that \(3m+2\) is the minimum order, which remained unproven. In this paper, using operation properties of sets and other methods, we prove that the minimum order of connected \(m-K_2\)-residual graphs is indeed \(3m+2\).

In this paper, we present explicit formulas for domination numbers of equidistant \(m\)-cactus chains and find the corresponding minimum dominating sets. For an arbitrary \(m\)-cactus chain, we establish the lower and upper bounds for its domination number. We find some extremal chains with respect to this graph invariant.

A strongly connected digraph \(D\) is said to be maximally arc connected if its arc-connectivity \(\lambda(D)\) attains its minimum degree \(\delta(D)\). For any vertex \(x\) of \(D\), the set \(\{x^g \mid g \in \text{Aut}(D)\}\) is called an orbit of \(\text{Aut}(D)\). Liu and Meng [ Fengxia Liu, Jixiang Meng, Edge-Connectivity of regular graphs with two orbits, Discrete Math. \(308 (2008) 3711-3717 \)] proved that the edge-connectivity of a \(k\)-regular connected graph with two orbits and girth \(\geq 5\) attains its regular degree \(k\). In the present paper, we prove the existence of \(k\)-regular \(m\)-arc-connected digraphs with two orbits for some given integer \(k\) and \(m\). Furthermore, we prove that the \(k\)-regular connected digraphs with two orbits, satisfying girth \( \geq k\) are maximally arc connected. Finally, we give an example to show that the girth bound \(k\) is best possible.

Let \(G\) be a graph with a vertex coloring. A colorful path is a path with \(\chi(G)\) vertices, in which the vertices have different colors. A colorful path starting at vertex \(v\) is a colorful \(v\)-path. We show that for every graph \(G\) and given vertex \(v\) of \(G\), there exists a proper vertex coloring of \(G\) with a colorful path starting at \(v\). Let \(G\) be a connected graph with maximum degree \(\Delta(G)\) and \(|V(G)| \geq 2\). We prove that there exists a proper \((\chi(G) + \Delta(G) – 1)\)-coloring of \(G\) such that for every \(v \in V(G)\), there is a colorful \(v\)-path.

Let \(\mathcal{B}(n,d)\) be the set of bicyclic graphs with both \(n\) vertices and diameter \(d\), and let \(\theta^*\) consist of three paths \(u_0w_1v_0\), \(u_0w_2v_0\), and \(u_0w_3v_0\). For four nonnegative integers \(n,d,k,j\) satisfying \(n \geq d+3\), \(d=k+j+2\), we let \(B(n,d;k,j)\) denote the bicyclic graph obtained from \(\theta^*\) by attaching a path of length \(k\) to \(u_0\), attaching a path of length \(j\) to vertex \(v_0\) and \(n-d-3\) pendant edges to \(w_0\), and let \(\mathcal{B}(n,d;k,j) = \{B(n,d;k,j) \mid k+j \geq 1\}\). In this paper, the extremal graphs with the minimal least eigenvalue among all graphs in \(\mathcal{B}(n,d;k,j)\) are well characterized, and some structural characterizations about the extremal graphs with the minimal least eigenvalue among all graphs in \(\mathcal{B}(n,d)\) are presented as well.

If \(G = (V, E)\) is a simple connected graph and \(a, b \in V\), then a shortest \((a – b)\) path is called an \((a – b)\)-geodesic. A set \(X \subseteq V\) is called weakly convex in \(G\) if for every two vertices \(a, b \in X\) there exists an \((a – b)\)-geodesic whose all vertices belong to \(X\). A set \(X\) is convex in \(G\) if for every \(a, b \in X\) all vertices from every \((a – b)\)-geodesic belong to \(X\). The weakly convex domination number of a graph \(G\) is the minimum cardinality of a weakly convex dominating set in \(G\), while the convex domination number of a graph \(G\) is the minimum cardinality of a convex dominating set in \(G\). In this paper, we consider weakly convex and convex domination numbers of Cartesian products, joins, and coronas of some classes of graphs.

Using a new way to label edges in a bicoloured ordered tree,we introduce a bijection between bicoloured ordered trees and non-nesting partitions. Consequently, enumerative results of non-nesting partitions are derived. Together with another bijection given before, we obtain a bijection between non-nesting partitions and non-crossing partitions specified with four parameters.