Given a (directed) graph \(G = (V,A)\), the induced subgraph of \(G\) by a subset \(X\) of \(V\) is denoted by \(G[X]\). A graph \(G = (V, A)\) is a \({tournament}\) if for any distinct vertices \(x\) and \(y\) of \(G\), \(G[\{x, y\}]\) possesses a single arc. With each graph \(G = (V,A)\), associate its \({dual}\) \(G^* = (V, A^*)\) defined as follows: for \(x,y \in V\), \((x,y) \in A^*\) if \((y,x) \in A\). Two graphs \(G\) and \(H\) are \({hemimorphic}\) if \(G\) is isomorphic to \(H\) or to \(H^*\). Moreover, let \(k > 0\). Two graphs \(G = (V,A)\) and \(H = (V,B)\) are \({k\;-hemimorphic}\) if for every \(X \subseteq V\), with \(|X| \leq k\), \(G[X]\) and \(H[X]\) are hemimorphic. A graph \(G\) is \({k\;-forced}\) when \(G\) and \(G^*\) are the only graphs \(k\)-hemimorphic to \(G\). Given a graph \(G = (V,A)\), a subset \(X\) of \(V\) is an \({interval}\) of \(G\) provided that for \(a,b \in X\) and \(x \in V\setminus X\), \((a,x) \in A\) if and only if \((b,x) \in A\), and similarly for \((x,a)\) and \((x,b)\). For example, \(\emptyset\), \(\{x\}\), where \(x \in V\), and \(V\) are intervals called trivial. A graph \(G = (V, A)\) is \({indecomposable}\) if all its intervals are trivial. Boussairi, Tle, Lopez, and Thomassé \([2]\) established the following duality result. An indecomposable graph which does not contain the graph \(({0, 1, 2}, {(0, 1), (1,0), (1,2)})\) and its dual as induced subgraphs is \(3\)-forced. A simpler proof of this theorem is provided in the case of tournaments and also in the general case. The \(3\)-forced graphs are then characterized.

Let \(G_i\) be the subgraph of \(G\) whose edges are in the \(i\)-th color in an \(r\)-coloring of the edges of \(G\). If there exists an \(r\)-coloring of the edges of \(G\) such that \(H_i \cong G_i\) for all \(1 \leq i \leq r\), then \(G\) is said to be \(r\)-colorable to \((H_1, H_2, \ldots, H_r)\). The multicolor Ramsey number \(R(H_1, H_2, \ldots, H_r)\) is the smallest integer \(n\) such that \(K_n\) is not \(r\)-colorable to \((H_1, H_2, \ldots, H_r)\). Let \(C_m\) be a cycle of length \(m\). The four-color Ramsey numbers related to \(C_6\) are studied in this paper. It is well known that \(18 \leq R_4( C_6) \leq 21\). We prove that \(R(C_5, C_4, C_4, C_4) = 19\) and \(18 \leq R(C_6, C_6, H_1, H_2) \leq 20\), where \(H_i\) are isomorphic to \(C_4\) or \(C_6\).

A graph \(G\) is called an \(M_r(k)\)-graph if \(G\) has no \(k\)-list assignment to its vertices with exactly \(r\) vertex colorings. We characterize all \(M_3(2)\)-graphs. More precisely, it is shown that a connected graph \(G\) is an \(M_3(2)\)-graph if and only if each block of \(G\) is a complete graph with at least three vertices.

A global boundary defensive \(k\)-alliance in a graph \(G = (V, E)\) is a dominating set \(S\) of vertices of \(G\) with the property that every vertex in \(S\) has \(\geq k\) more neighbors in \(S\) than it has outside of \(S\). A global boundary offensive \(k\)-alliance in a graph \(G\) is a set \(S\) of vertices of \(G\) with the property that every vertex in \(V \setminus S\) has \(k\) more neighbors in \(S\) than it has outside of \(S\). We define a global boundary powerful \(k\)-alliance as a set \(S\) of vertices of \(G\), which is both global boundary defensive \(k\)-alliance and global boundary offensive \((k+2)\)-alliance. In this paper, we study mathematical properties of boundary powerful \(k\)-alliances. In particular, we obtain several bounds (closed formulas for the case of regular graphs) on the cardinality of every global boundary powerful \(k\)-alliance. Additionally, we consider the case in which the vertex set of a graph \(G\) can be partitioned into two boundary powerful \(k\)-alliances, showing that, in such a case, \(k = -1\) and, if \(G\) is \(\delta\)-regular, its algebraic connectivity is equal to \(\delta + 1\).

We present two recursive enumeration formulas for the number of labelled essential graphs. The enumeration parameters of the first formula are the number of vertices, chain components, and cliques, while the enumeration parameters of the second formula are the number of vertices and cliques.Both formulas may be used to count the number of labelled essential graphs
with given number of vertices.

In this paper, we first survey the connections between Bell polynomials (numbers) and the derangement polynomials (numbers). Their close relations are mainly based on Hsu’ summation formula. According to this formula, we present some new identities involving harmonic numbers,Bell polynomials (numbers) and the derangement polynomials (numbers).Moreover, we find that the series \(\sum_{m\geq0}(\frac{D_m}{m!}-\frac{1}{e})\) is (absolutely) convergent and their sums are also determined, where \(D_m\) is the \(mth\) derangement number.

A graph \(G\) is regular if the degree of each vertex of \(G\) is d and almost regular or more precisely a \((d,d + 1)\)-graph, if the degree of each vertex of \(G\) is either \(d\) or \(d+1\). If \(d \geq 2\) is an integer, \(G\) a triangle-free \((d,d + 1)\)-graph of order n without an odd component and \(n \leq 4d\), then we show in this paper that \(G\) contains a perfect matching. Using a new Turdn type result, we present an analogue for triangle-free regular graphs. With respect to these results, we construct smallest connected, regular and almost regular triangle-free even order graphs without perfect matchings.

In a search for triangle-free graphs with arbitrarily large chromatic numbers, Mycielski developed a graph transformation that transforms a graph \(G\) into a new graph \(\mu(G)\), which is called the Mycielskian of \(G\).This paper shows that:
For a strongly connected digraph \(D\) with \(|V(D)| \geq 2\):\(\mu(D)\) is super-\(\kappa\) if and only if \(\delta(D) < 2\kappa(D)\).;\(\mu(D)\) is super-\(\lambda\) if and only if \(D \ncong \overrightarrow{K_2}\).

The sum of the squares of eccentricity \((SSE)\) over all vertices of a connected graph is a new graph invariant proposed in \([13]\) and further studied in \([14, 15]\). In this paper, we report some further mathematical properties of \(SSE\). We give sharp lower bounds for \(SSE\) among all \(n\)-vertices connected graphs with given independence number, vertex-, and edge-connectivity, respectively. Addtionally, we give explicit formulas for \(SSE\) of Cartesian product of two graphs, from which we deduce \(SSE\) of \(C_4\), nanotube and nanotorus.

The vertex linear arboricity \(vla(G)\) of a nonempty graph \(G\) is the minimum number of subsets into which the vertex set \(V(G)\) can be partitioned so that each subset induces a subgraph whose connected components are paths.An integer distance graph is a graph \(G(D)\) with the set of all integers as vertex set and two vertices \(u,v \in {Z}\) are adjacent if and only if \(|u-v| \in D\), where the distance set \(D\) is a subset of the positive integers.Let \(D_{m,k,3} = [1,m] \setminus \{k, 2k, 3k\}\) for \(m \geq 4k \geq 4\). In this paper, we obtain some upper and lower bounds of the vertex linear arboricity of the integer distance graph \(G(D_{m,k,3})\) and the exact value of it for some special cases.