We first establish the relationship between the largest eigenvalue of the Laplacian matrix of a graph and its bipartite density. Then, we present lower and upper bounds for the largest Laplacian eigenvalue of a graph in terms of its largest degree and diameter.

In this paper, we prove the gracefulness of the class of graphs denoted by \(\mathcal{P}_{a,b}\).

Let \(D\) be a dominating set of a simple graph \(G = (V, E)\). If the subgraph \((V – D)_G\)induced by the set \(V – D\) is disconnected, then \(D\) is called a split dominating set of \(G\), and if \(\langle D\rangle_G\) has no edges, then \(D\) is an independent dominating set of \(G\). If every vertex in \(V\) is adjacent to some vertex of \(D\) in \(G\), then \(D\) is a total dominating set of \(G\). The split domination number \(\gamma_s(G)\), independent domination number \(i(G)\), and total domination number \(\gamma_t(G)\) equal the minimum cardinalities of a split, independent, and total dominating set of \(G\), respectively. The concept of split domination was first defined by Kulli and Janakiram in 1997 [4], while total domination was introduced by Cockayne, Dawes, and Hedetniemi in 1980 [2].

In this paper, we study the split, independent, and total domination numbers of corona \(G \circ H\) and generalized coronas \(kG \circ H\) of graphs.

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.