In [13], we conjectured that if \(G = (V_1, V_2; E)\) is a bipartite graph with \(|V_1| = |V_2| = 2k\) and minimum degree at least \(k + 1\), then \(G\) contains \(k\) vertex-disjoint quadrilaterals. In this paper, we propose a more general conjecture: If \(G = (V_1, V_2; E)\) is a bipartite graph such that \(|V_1| = |V_2| = n \geq 2\) and \(\delta(G) \geq [n/2] + 1\), then for any bipartite graph \(H = (U_1, U_2; F)\) with \(|U_1| \leq n, |U_2| \leq n\) and \(\Delta(H) \leq 2, G\) contains a subgraph isomorphic to \(H\). To support this conjecture, we prove that if \(n = 2k + t\) with \(k \geq 0\) and \(t \geq 3, G\) contains \(k + 1\) vertex-disjoint cycles covering all the vertices of \(G\) such that \(k\) of them are quadrilaterals.

In a finite projective plane, a \(k\)-arc \(\mathcal{K}\) covers a line \(l_0\) if every point on \(l_0\) lies on a secant of \(\mathcal{K}\). Such \(k\)-arcs arise from determining sets of elements for which no linear \((n, q, t)\)-perfect hash families exist [1], as well as from finding sets of points in \(\mathrm{AG}(2, q)\) which determine all directions [2]. This paper provides a lower bound on \(k\) and establishes exactly when the lower bound is attained. This paper also gives constructions of such \(k\)-arcs with \(k\) close to the lower bound.

In this paper we determine the \(k\)-domination number \(\gamma_k\) of \(P_{2k+2} \times P_n\) and \(\lim_{{m,n} \to \infty} \frac{\Gamma_k(P_m \times P_n)}{mn}\).

A digraph obtained by replacing each edge of a complete \(n\)-partite graph by an arc or a pair of mutually opposite arcs is called a semi-complete \(n\)-partite digraph. An \(n\)-partite tournament is an orientation of a complete \(n\)-partite graph. In this paper we shall prove that a strongly connected semicomplete \(n\)-partite digraph with a longest directed cycle \(C\), contains a spanning strongly connected \(n\)-partite tournament which also has the longest directed cycle \(C\) with exception of a well determined family of semicomplete bipartite digraphs. This theorem shows that many well-known results on strongly connected \(n\)-partite tournaments are also valid for strongly connected semicomplete \(n\)-partite digraphs.

Let \(k\) be a positive integer and let \(G\) be a graph. For two distinct vertices \(x, y \in V(G)\), the \(k\)-wide-distance \(d_k(x, y)\) between \(x\) and \(y\) is the minimum integer \(l\) such that there exist \(k\) vertex-disjoint \((x, y)\)-paths whose lengths are at most \(l\). We define \(d_k(x, x) = 0\). The \(k\)-wide-diameter \(d_k(G)\) of \(G\) is the maximum value of the \(k\)-wide-distance between two vertices of \(G\). In this paper we show that if \(G\) is a graph with \(d_k(G) \geq 2\) (\(k \geq 3\)), then there exists a cycle which contains specified \(k\) vertices and has length at most \(2(k – 3)(\operatorname{d_k}(G) – 1) + \max\{3d_k(G), \lfloor\frac{18d_k(G)-16}{5}\rfloor \}\).

Let \(G_1\) and \(G_2\) be two graphs of the same size such that \(V(G_1) = V(G_2)\), and let \(H\) be a connected graph of order at least \(3\). The graphs \(G_1\) and \(G_2\) are \(H\)-adjacent if \(G_1\) and \(G_2\) contain copies \(H_1\) and \(H_2\) of \(H\), respectively, such that \(H_1\) and \(H_2\) share some but not all edges and \(G_2 = G_1 – E(H_1) + E(H_2)\). The graphs \(G_1\) and \(G_2\) are \(H\)-connected if \(G_1\) can be obtained from \(G_2\) by a sequence of \(H\)-adjacencies. The relation \(H\)-connectedness is an equivalence relation on the set of all graphs of a fixed order and fixed size. The resulting equivalence classes are investigated for various choices of the graph \(H\).

A generalized \(p\)-cycle is a digraph whose set of vertices is partitioned in \(p\) parts that are cyclically ordered in such a way that the vertices in one part are adjacent only to vertices in the next part. In this work, we mainly show the two following types of conditions in order to find generalized \(p\)-cycles with maximum connectivity:

1. For a new given parameter \(\epsilon\), related to the number of short paths in \(G\), the diameter is small enough.

2. Given the diameter and the maximum degree, the number of vertices is large enough.

For the first problem it is shown that if \(D \leq 2\ell + p – 2\), then the connectivity is maximum. Similarly, if \(D \leq 2\ell + p – 1\), then the edge-connectivity is also maximum. For problem two an appropriate lower bound on the order, in terms of the maximum and minimum degree, the parameter \(\ell\) and the diameter is deduced to guarantee maximum connectivity.

For a graph \(G = (V, E)\) and \(X \subseteq V(G)\), let \(\operatorname{dist}_G(u, v)\) be the distance between the vertices \(u\) and \(v\) in \(G\) and \(\sigma_3(X)\) denote the minimum value of the degree sum (in \(G\)) of any three pairwise non-adjacent vertices of \(X\). We obtain the main result: If \(G\) is a \(1\)-tough graph of order \(n\) and \(X \subseteq V(G)\) such that \(\sigma_3(X) \geq n\) and, for all \(x, y \in X\), \(\operatorname{dist}_G(x, y) = 2\) implies \(\max\{d(x), d(y)\} \geq \frac{n-4}{2}\), then \(G\) has a cycle \(C\) containing all vertices of \(X\). This result generalizes a result of Bauer, Broersma, and Veldiman.