In this paper we consider the problem as follows: Given a bipartite graph \(G = (V_1, V_2; E)\) with \(|V_1| = |V_2| = n\) and a positive integer \(k\), what degree condition is sufficient to ensure that for any \(k\) distinct vertices \(v_1, v_2, \ldots, v_k\) of \(G\), \(G\) contains \(k\) independent quadrilaterals \(Q_1, Q_2, \ldots, Q_k\) such that \(v_i \in V(Q_i)\) for every \(i \in \{1, 2, \ldots, k\}\), or \(G\) has a \(2\)-factor with \(k\) independent cycles of specified lengths with respect to \(\{v_1, v_2, \ldots, v_k\}\)? We will prove that if \(d(x) + d(y) \geq \left\lceil (4n + k)/3 \right\rceil\) for each pair of nonadjacent vertices \(x \in V_1\) and \(y \in V_2\), then, for any \(k\) distinct vertices \(v_1, v_2, \ldots, v_k\) of \(G\), \(G\) contains \(k\) independent quadrilaterals \(Q_1, Q_2, \ldots, Q_k\) such that \(v_i \in V(Q_i)\) for each \(i \in \{1, \ldots, k\}\). Moreover, \(G\) has a \(2\)-factor with \(k\) cycles with respect to \(\{v_1, v_2, \ldots, v_k\}\) such that \(k – 1\) of them are quadrilaterals. We also discuss the degree conditions in the above results.

We call the graph \(G\) an edge \(m\)-coloured if its edges are coloured with \(m\) colours. A path (or a cycle) is called monochromatic if all its edges are coloured alike. A subset \(S \subseteq V(G)\) is independent by monochromatic paths if for every pair of different vertices from \(S\) there is no monochromatic path between them. In \([5]\) it was defined the Fibonacci number of a graph to be the number of all independent sets of \(G\); recall that \(S\) is independent if no two of its vertices are adjacent. In this paper we define the concept of a monochromatic Fibonacci number of a graph which gives the total number of monochromatic independent sets of \(G\). Moreover we give the number of all independent by monochromatic paths sets of generalized lexicographic product of graphs using the concept of a monochromatic Fibonacci polynomial of a graph. These results generalize the Fibonacci number of a graph and the Fibonacci polynomial of a graph.

Let \(D = (V, E)\) be a primitive digraph. The exponent of \(D\) at a vertex \(u \in V\), denoted by \(\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 \(\exp_D(v_{i_1}) \leq \exp_D(v_{i_2}) \leq \ldots \leq \exp_D(v_{i_n}) = \gamma(D)\). The number \(\exp_p(v_n)\) is called the \(k\)-exponent of \(D\), denoted by \(\exp_p(k)\). We use \(L(D)\) to denote the set of distinct lengths of the cycles of \(D\). In this paper, we completely determine the \(1\)-exponent sets of primitive, minimally strong digraphs with \(n\) vertices and \(L(D) = \{p, q\}\), where \(3 \le p < q\) and \(p + q > n\).

Let \(\mathcal{C}\) be any class of finite graphs. A graph \(G\) is \(\mathcal{C}\)-ultrahomogeneous if every isomorphism between induced subgraphs belonging to \(\mathcal{C}\) extends to an automorphism of \(G\). We study finite graphs that are \({K}_*\)-ultrahomogeneous, where \({K}_*\) is the class of complete graphs. We also explicitly classify the finite graphs that are \(\sqcup{K}_{*}\)-ultrahomogeneous, where \(\sqcup{K}_{*}\) is the class of disjoint unions of complete graphs.

For any positive integer \(n\), let \(S_n\), denote the set of all permutations of the set \(\{1,2,\ldots,n\}\). We think of a permutation just as an ordered list. For any \(p\) in \(S_n\), and for any \(i \leq n\), let \(p \downarrow i\) be the permutation on the set \(\{1,2,\ldots,n – 1\}\) obtained from \(p\) as follows: delete \(i\) from \(p\) and then subtract \(1\) in place from each of the remaining entries of \(p\) which are larger than \(i\). For any \(p\) in \(S_n\), we let \(R(p) = \{q \in S_{n-1} : g = p \downarrow i \;\text{for some} \;i \leq n\}\), the set of reductions of \(p\). It is shown that, for \(n > 4\), any \(p\) in \(S_n\), is determined by its set of reductions \(R(p)\).