Let \(L\) and \(R\) be two graphs. For any positive integer \(n\), the Ehrenfeucht-Fraissé game \(G_n(L, R)\) is played as follows: on the \(i\)-th move, with \(1 \leq i \leq n\), the first player chooses a vertex on either \(L\) or \(R\), and the second player responds by choosing a vertex on the other graph. Let \(l_i\) be the vertex of \(L\) chosen on the \(i^{th}\) move, and let \(r_i\) be the vertex of \(R\) chosen on the \(i^{th}\) move. The second player wins the game iff the induced subgraphs \(L\{l_1,l_2,…,l_n\}\) and \(R\{r_1,r_2,…,r_n\}\) are isomorphic under the mapping sending \(l_i\) to \(r_i\). It is known that the second player has a winning strategy if and only if the two graphs, viewed as first-order logical structures (with a binary predicate E), are indistinguishable (in the corresponding first-order theory) by sentences of quantifier depth at most \(n\). In this paper we will give the first complete description of when the second player has a winning strategy for \(L\) and \(R\) being both paths or both cycles. The results significantly improve previous partial results.

By applying the method of generating function, the purpose of this paper is to give several summations of reciprocals related to \(l-th\) power of generalized Fibonacci sequences. As applications, some identities involving Fibonacci, Lucas numbers are obtained.

Bricks are polyominoes with labelled cells. The problem whether a given set of bricks is a code is undecidable in general. We consider sets consisting of square bricks only. We have shown that in this setting, the codicity of small sets (two bricks) is decidable, but \(15\) bricks are enough to make the problem undecidable. Thus the step from words to even simple shapes changes the algorithmic properties significantly (codicity is easily decidable for words). In the present paper we are interested whether this is reflected by quantitative properties of words and bricks. We use their combinatorial properties to show that the proportion of codes among all sets is asymptotically equal to \(1\) in both cases.

Let \(G_{n,m} = C_n \times P_m\), be the cartesian product of an \(n\)-cycle \(C_n\) and a path \(P_m\) of length \(m-1\). We prove that \(\chi'(G_{n,m}) = \chi'(G_{n,m}) = 4\) if \(m \geq 3\), which implies that the list-edge-coloring conjecture (LLECC) holds for all graphs \(G_{n,m}\).

Various authors have defined statistics on Dyck paths that lead to generalizations of the Catalan numbers. Three such statistics are area, maj, and bounce. Haglund, whe introduced the bounce statistic, gave an algebraic proof that \(n(n – 1)/2+\) area — bounce and maj have the same distribution on Dyck paths of order \(n\). We give an explicit bijective proof of the same result.

We develop a new type of a vertex labeling of graphs, namely \(2n\)-cyclic blended labeling, which is a generalization of some previously known labelings. We prove that a graph with this labeling factorizes the complete graph on \(2nk\) vertices, where \(k\) is odd and \(n, k > 1\).

Let \(D = (V, E)\) be a primitive digraph. The exponent of \(D\) at a vertex \(u \in V\), denoted by \(\text{exp}_D(u)\), is defined to be the least integer \(k\) such that there is a walk of length \(k\) from \(u\) to \(v\) for each \(v \in V\). Let \(V = \{v_1,v_2,\ldots ,v_n\}\). The vertices of \(V\) can be ordered so that \(\text{exp}_D(v_{i_1}) \leq \text{exp}_D(v_{i_2}) \leq \ldots \leq \text{exp}_D(v_{i_n})\). The number \(\text{exp}_D(v_{i_k})\) is called \(k\)-exponent of \(D\), denoted by \(\text{exp}_D(k)\). In this paper, we completely characterize \(1\)-exponent set of primitive, minimally strong digraphs with \(n\) vertices.

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