In \([4]\) H. Galana-Sanchez introduced the concept of kernels by monochromatic paths which generalize the concept of kernels. In \([6]\) they proved the necessary and sufficient conditions for the existence of kernels by monochromatic paths of the duplication of a subset of vertices of a digraph, where a digraph is without monochromatic directed circuits. In this paper we study independent by monochromatic paths sets and kernels by monochromatic paths of the duplication. We generalize result from \([6]\) for an arbitrary edge coloured digraph.

Let \(D = (V, E)\) be a primitive, minimally strong digraph. In \(1982\), J. A. Ross studied the exponent of \(D\) and obtained that \(\exp(D) \leq n + s(n – 8)\), where \(s\) is the length of a shortest circuit in \(D\) \([D]\). In this paper, the \(k\)-exponent of \(D\) is studied. Our principle result is that
\[
\exp_D(k) \leq \begin{cases}
k + 1 + s(n – 3), & \text{if } 1 \leq k \leq s, \\\
k + s(n-3), & \text{if } s+1 \leq k \leq n,\\
\end{cases} \\.
\]
with equality if and only if \(D\) isomorphic to the diagraph \(D_{s,n}\) with vertex set \(V(D_{s,n})=\{v_1,v_2,\ldots,v_n\}\) and arc set \(E(D_{s,n})=\{(v_i,v_{i+1}):1\leq i\leq n-1\}\cap \{(v_s,v_1),(v_n,v_2)\}\). If \((s,n-1)\neq 1\),then
\[
\exp_D(k)< \begin{cases} k + 1 + s(n – 3), & \text{if } 1 \leq k \leq s, \\\ k + s(n-3), & \text{if } s+1 \leq k \leq n, \end{cases} \\ \] and if \((s,n-1)=1\), then \(D_{s, n}\) is a primitive, minimally strong digraph on \(n\) vertices with the \(k\)-exponent \[ \exp_D(k)= \begin{cases} k + 1 + s(n – 3), & \text{if } 1 \leq k \leq s, \\\ k + s(n-3), & \text{if } s+1 \leq k \leq n, \end{cases} \\ \] Moreover, we provide a new proof of Theorem \(1\) in \([6]\) and Theorem \(2\) in \([14]\) by applying this result.

Given a finite projective plane of order \(n\). A quadrangle consists of four points \(A, B, C, D\), no three collinear. If the diagonal points are non-collinear, the quadrangle is called a non-Fano quad. A general sum of squares theorem is proved for the distribution of points in a plane containing a non-Fano quad, whenever \(n \geq 7\). The theorem implies that the number of possible distributions of points in a plane of order \(n\) is bounded for all \(n \geq 7\). This is used to give a simple combinatorial proof of the uniqueness of \(PP(7)\).

Let \(G = (V, E)\) be a graph with \(n\) vertices. The clique graph of \(G\) is the intersection graph \(K(G)\) of the set of all (maximal) cliques of \(G\) and \(K\) is called the clique operator. The iterated clique graphs \(K^*(G)\) are recursively defined by \(K^0(G) = G\) and \(K^i(G) = K(K^{i-1}(G))\), \(i > 0\). A graph is \(K\)-divergent if the sequence \(|V(K^i(G))|\) of all vertex numbers of its iterated clique graphs is unbounded, otherwise it is \(K\)-convergent. The long-run behaviour of \(G\), when we repeatedly apply the clique operator, is called the \(K\)-behaviour of \(G\).

In this paper, we characterize the \(K\)-behaviour of the class of graphs called \(p\)-trees, that has been extensively studied by Babel. Among many other properties, a \(p\)-tree contains exactly \(n – 3\) induced \(4\)-cycles. In this way, we extend some previous results about the \(K\)-behaviour of cographs, i.e., graphs with no induced \(P_4\)s. This characterization leads to a polynomial-time algorithm for deciding the \(K\)-convergence or \(K\)-divergence of any graph in the class.

In this paper, we obtain a general enumerating functional equation about rooted pan-fan maps on nonorientable surfaces. Based on this equation, an explicit expression of rooted pan-fan maps on the Klein bottle is given. Meanwhile, some simple explicit expressions with up to two parameters: the valency of the root face and the size for rooted one-vertexed maps on surfaces (Klein bottle, Torus, \(N_3\)) are provided.

Let us denote by \({EX}(m,n; \{C_4,\ldots,C_{2t}\})\) the family of bipartite graphs \(G\) with \(m\) and \(n\) vertices in its classes that contain no cycles of length less than or equal to \(2t\) and have maximum size. In this paper, the following question is proposed: does always such an extremal graph \(G\) contain a \((2t + 2)\)-cycle? The answer is shown to be affirmative for \(t = 2,3\) or whenever \(m\) and \(n\) are large enough in comparison with \(t\). The latter asymptotical result needs two preliminary theorems. First, we prove that the diameter of an extremal bipartite graph is at most \(2t\), and afterwards we show that its girth is equal to \(2t + 2\) when the minimum degree is at least \(2\) and the maximum degree is at least \(t + 1\).

In Algebraic Graph Theory, Biggs \([2]\) gives a method for finding the chromatic polynomial of any connected graph by computing the Tutte polynomial. It is used by Biggs \([2]\) to compute the chromatic polynomial of Peterson’s graph. In \(1972\) Sands \([4]\) developed a computer algorithm using matrix operations on the incidence matrix to compute the Tutte Polynomial. In \([1]\), Anthony finds the worst-case time-complexity of computing the Tutte Polynomial. This paper shows a method using group-theoretical properties to compute the Tutte polynomial for Cayley graphs which improves the time-complexity.

Let \(N({Z})\) denote the set of all positive integers (integers). The sum graph \(G_S\) of a finite subset \(S \subset N({Z})\) is the graph \((S, E)\) with \(uv \in E\) if and only if \(u+v \in S\). A graph \(G\) is said to be an (integral) sum graph if it is isomorphic to the sum graph of some \(S \subset N({Z})\). The (integral) sum number \(\sigma(G)\) of \(G\) is the smallest number of isolated vertices which when added to \(G\) result in an (integral) sum graph. A mod (integral) sum graph is a sum graph with \(S \subset {Z}_m \setminus \{0\}\) (\(S \subset {Z}_m\)) and all arithmetic performed modulo \(m\) where \(m \geq |S|+1\) (\(m \geq |S|\)). The mod (integral) sum number \(\rho(G)\) of \(G\) is the least number \(\rho\) (\(\psi\)) of isolated vertices \(\rho K_1\) (\(\psi K_1\)) such that \(G \cup \rho K_1\) (\(G \cup \psi K_1\)) is a mod (integral) sum graph. In this paper, the mod (integral) sum numbers of \(K_{r,s}\) and \(K_n – E(K_r)\) are investigated and bounded, and \(n\)-spoked wheel \(W_n\) is shown to be a mod integral sum graph.

In this paper, the forcing domination numbers of the graphs \(P_n \times P_3\) and \(C_n \times P_3\) are completely determined. This improves the previous results on the forcing domination numbers of \(P_n \times P_2\) and \(C_n \times P_2\).