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.

Some constructions of affine \((\alpha_1, \ldots, \alpha_n)\)-resolvable \((r, \lambda)\)-designs are discussed, by use of affine \(\alpha\)-resolvable balanced incomplete block designs or semi-regular group divisible designs. A structural property is also indicated.

We establish a connection between the principle of inclusion-exclusion and the union-closed sets conjecture. In particular, it is shown that every counterexample to the union-closed sets conjecture must satisfy an improved inclusion-exclusion identity.

Broadcasting in a network is the process whereby information, initially held by one node, is disseminated to all nodes in the network. It is assumed that, in each unit of time, every vertex that has the information can send it to at most one of its neighbours that does not yet have the information. Furthermore, the networks considered here are of bounded (maximum) degree \(\Delta\), meaning that each node has at most \(\Delta\) neighbours. In this article, a new parameter, the average broadcast time, defined as the minimum mean time at which a node in the network first receives the information, is introduced. It is found that when the broadcast time is much greater than the maximum degree, the average broadcast time is (approximately) between one and two time units less than the total broadcast time if the maximum degree is at least three.

The path spectrum, \(\operatorname{sp}(G)\), of a graph \(G\) is the set of all lengths of maximal paths in \(G\). The path spectrum is continuous if \(\operatorname{sp}(G) = \{\ell, \ell1, \dots, \ell\}\) for some \(\ell \leq m\). A graph whose path spectrum consists of a single element is called scent and is by definition continuous. In this paper, we determine when a \(\{K_{1, 3}, S\}\)-free graph has a continuous path spectrum where \(S\) is one of \(C_3, P_4, P_5, P_6, Z_1, Z_2, Z_3, N, B\), or \(W\).

A graph \(G\) is \((p, q, r)\)-choosable if for every list assignment \(L\) with \(|L(v)| \geq p\) for each \(v \in V(G)\) and \(|L(u) \cap L(v)| < p – r\) whenever \(u, v\) are adjacent vertices, \(G\) is \(q\)-tuple \(L\)-colorable. We give an alternative proof of \((4t, t, 3t)\)-choosability for the planar graphs and construct a triangle-free planar graph on \(119\) vertices which is not \((3, 1, 1)\)-choosable (and so neither \(3\)-choosable). We also propose some problems.