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.

We study the behaviour of two domination parameters: the split domination number \(\gamma_s(G)\) of a graph \(G\) and the maximal domination number \(\gamma_m(G)\) of \(G\) after the deletion of an edge from \(G\). The motivation of these problems comes from [2]. In [6] Vizing gave an upper bound for the size of a graph with a given domination number. Inspired by [5] we formulate Vizing type relation between \(|E(G)|, |V(G)|, \Delta(G)\) and \(\delta(G)\), where \(\Delta(G)\) (\(\delta(G)\)) denotes the maximum (minimum) degree of \(G\).

A \(2\)-factor \(F\) of a bipartite graph \(G = (A, B; E)\), \(|A| = |B| = n\), is small if \(F\) comprises \(\lfloor \frac{n}{2}\rfloor\) cycles. A set \(\mathfrak{F}\) of small edge-disjoint \(2\)-factors of \(G\) is maximal if \(G – \mathfrak{F}\) does not contain a small \(2\)-factor. We study the spectrum of maximal sets of small \(2\)-factors.

The linear vertex-arboricity of a graph \(G\) is defined as the minimum number of subsets into which the vertex-set \(V(G)\) can be partitioned so that every subset induces a linear forest. In this paper, we give the upper and lower bounds for the sum and product of linear vertex-arboricity with independence number and with clique cover number, respectively. All of these bounds are sharp.