A set of points in a Steiner triple system (STS(\(v\))) is said to be independent if no three of these points occur in the same block. In this paper, we derive for each \(k \leq 8\) a closed formula for the number of independent sets of cardinality \(k\) in an STS(\(v\)). We use the formula to prove that every STS(21) has an independent set of cardinality eight and is, as a consequence, \(4\)-colourable.

Let \(G\) be a graph with \(n\) vertices and let \(D\) be a minimum dominating set of \(G\). If \(V – D\) contains a dominating set \(D’\) of \(G\), then \(D’\) is called an inverse dominating set of \(G\) with respect to \(D\). The inverse domination number \(\gamma'(G)\) of \(G\) is the cardinality of a smallest inverse dominating set of \(G\). In this paper, we characterise graphs for which \(\gamma(G) + \gamma'(G) = n\). We give a lower bound for the inverse domination number of a tree and give a constructive characterisation of those trees which achieve this lower bound.

Siri and Gvozdjak proved in [9] that the bananas surface, the pseudosurface consisting in the \(2\)-amalgamation of two spheres, does not admit a finite Kuratowski Theorem.

In this paper we prove that pseudosurfaces arising from the \(n\)-amalgamation of two closed surfaces, \(n \geq 2\), do not admit a finite Kuratowski Theorem, by showing an infinite family of minimal non-embeddable graphs.

We denote by \(K(l*r)\) the complete \(r\)-partite graph with \(l\) vertices in each part, and denote \(K(l*v)+K(m*s)+K(n*t)+\cdots\) by \(K(l*r,m*s,n*t,\ldots)\). Kierstead showed that the choice number of \(K(3*r)\) is exactly \(\left\lceil\frac{4r-1}{3}\right\rceil\). In this paper, we shall determine the choice number of \(K(3*r,1*t)\), and consider the choice number of \(K(3*r,2*s,1*t)\).

For any prime power \(q\), there exists an affine plane of order \(q\). The complement of an affine plane is a balanced incomplete block design (BIBD) with block size \(q^2-q\). In this note, a proof is given that the blocks can be split into sub-blocks to form a nested BIBD with parameters \((q^2, q^2+q, q^3+q^2, q^2-1,q-1)\). Alternatively, this is a generalized tournament design with one game each round, involving \(q\) teams, each team with \(q-1\) players.

Let \(\mathcal{F}\) be a family of \(k\)-graphs. A \(k\)-graph \(G\) is called \(\mathcal{F}\)-saturated if it is a maximal graph not containing any member of \(\mathcal{F}\) as a subgraph. We investigate the smallest number of edges that an \(\mathcal{F}\)-saturated graph on \(n\) vertices can have. We present new results and open problems for different instances of \(\mathcal{F}\).

A strongly regular vertex with parameters \((\lambda, \mu)\) in a graph is a vertex \(x\) such that the number of neighbors any other vertex \(y\) has in common with \(x\) is \(\lambda\) if \(y\) is adjacent to \(x\), and is \(\mu\) if \(y\) is not adjacent to \(x\). In this note, we will prove some basic properties of these vertices and the graphs that contain them, as well as provide some simple constructions of regular graphs that are not necessarily strongly regular, but do contain many strongly regular vertices. We also make several conjectures and find all regular graphs on at most ten vertices with at least one strongly regular vertex.

Given \(S\) a benzenoid system, we find an expression of the second order Randić index, denoted by \(\mathop{^2\chi}(S)\), in terms of inlet features of \(S\). As a consequence, we classify benzenoid systems with equal \(\mathop{^2\chi}\) and then find the minimal and maximal value over the set of catacondensed systems.

Let \(m_1, m_2, \ldots, m_r\) be positive integers with \(m_i \geq 3\) for all \(i\). An \((m_1, m_2, \ldots, m_r)\)-cycle is defined as the edge-disjoint union of \(r\) cycles of lengths \(2m_1, 2m_2, \ldots, 2m_r\). An \((m_1, m_2, \ldots, m_r)\)-cycle system of the complete graph \(K_n\) is a decomposition of \(K_n\) into \((m_1, m_2, \ldots, m_r)\)-cycles.

In this paper, the necessary and sufficient conditions for the existence of an \((m_1, m_2, \ldots, m_r)\)-cycle system of \(K_n\) are given, where \(m_i\) \((1 \leq i \leq r)\) are odd integers with \(3 \leq m_i \leq n\) and \(\sum_{i=1}^r m_i = 2^k\) for \(k \geq 3\). Moreover, the complete graph with a \(1\)-factor removed \(K_n – F\) has a similar result.

We refer to a labeling of a plane graph as a d-antimagic labeling if the vertices, edges and faces of the graph are labeled in such a way that the label of a face and the labels of vertices and edges surrounding that face add up to a weight of the face and the weights
of faces constitute an arithmetical progression of difference \(d\). In this paper we deal with \(d\)-antimagic labeling of prisms.