Bicyclic graphs are connected graphs in which the number of edges equals the number of vertices plus one. In this paper, we determine the first three graphs among all bicyclic graphs with \(n\) vertices, ordered according to their least eigenvalues in increasing order.

The modified Zagreb indices are topological indices which reflect certain structural features of organic molecules. In this paper we study the modified Zagreb indices of joins and compositions.

In \([1]\), well-ordered Steiner triple systems were introduced and used to construct \(1\)-perfect partitions of the \(n\)-cube. However, non-trivial well-ordered Steiner triple systems were only known to exist when \(v =15\). In this short note, we present a simple construction to give a non-trivial well-ordered Steiner triple system of order \(v = 2^n – 1\) for all \(n \geq 5\) and this settles a problem in \([1]\).

Different neighbor conditions are considered in \([3,4,9]\) for a graph up-embeddable. In this paper, we consider the neighbor conditions of all the pairs of vertices with diameter \(2\) and obtain the following new result: if \(|N_G(u) \cap N_G(v)| \geq 2\) for any two vertices \(u,v \in D\) where \(D = \{(u, v) | d_G(u, v) = 2, u,v \in V(G)\}\), then \(G\) is up-embeddable.

We study the factorisations of a cyclic permutation of length \(n\) as a product of a minimal number of transpositions, calculating the number \(f(n, m)\) of factorisations in which a fixed element is moved \(m\) times. In this way, we also give a new proof-in the spirit of Clarke’s proof of Cayley’s theorem on the number of labelled trees-of the fact that there are \(n^{n-2}\) such factorisations.

We show that there are relationships between a generalized Lucas sequence and the permanent and determinant of some Hessenberg matrices.

Suppose \(G\) is a simple graph with average vertex degree greater than \(k – 2\). Erdős and Sós conjectured that \(G\) contains every tree on \(k\) vertices. Sidorenko proved \(G\) contains every tree that has a vertex \(v\) with at least \(\left\lfloor\frac{k}{2}\right\rfloor – 1\) leaf neighbors. We prove this is true if \(v\) has only \(\left\lceil\frac{k}{2}\right\rceil – 2\) leaf neighbors. We generalize Sidorenko’s result by proving that if \(G\) has minimum degree \(d\), then \(G\) contains every tree that has a vertex with at least \((k – 1) – d\) leaf neighbors. We use these results to prove that if \(G\) has average degree greater than \(k – 2\) and minimum degree at least \(k – 4\), then \(G\) contains every tree on \(k\) vertices.

A simple graph \(G\)is induced matching extendable, shortly IM-extendable, if every induced matching of \(G\) is included in a perfect matching of \(G\). The cyclic graph \(C_{2n}(1,k)\) is the graph with \(2n\) vertices \(x_0, x_1, \ldots, x_{2n-1}\), such that \(x_ix_j\) is an edge of \(C_{2n}(1,k)\) if either \(i-j \equiv \pm 1 \pmod{2n}\) or \(i-j \equiv \pm k \pmod{2n}\). We show in this paper that the only IM-extendable graphs in \(C_{2n}(1,k)\) are \(C_{2n}(1,3)\) for \(n \geq 4\); \(C_{2n}(1,n-1)\) for \(n \geq 3\); \(C_{2n}(1,n)\) for \(n \geq 2\); \(C_{2n}(1,\frac{n}{2})\) for \(n \geq 4\); \(C_{2n}(1,\frac{2n+1}{3})\) for \(n \geq 5\); \(C_{2n}(1,\frac{2n+2}{3})\) for \(n \leq 14\); \(C_{2n}(1,\frac{2n-2}{3})\) for \(n \leq 16\); \(C_{2n}(1,2)\) for \(n \leq 4\); \(C_{20}(1,8)\); \(C_{30}(1,6)\); \(C_{40}(1,8)\); \(C_{60}(1,12)\) and \(C_{80}(1,10)\).

For a vertex \(v\) in a graph \(G\), a local cut at \(v\) is a set of size \(d(v)\) consisting of the vertex \(x\) or the edge \(vx\) for each \(x \in N(v)\). A set \(U \subseteq V(G) \cup E(G)\) is a diameter-increasing set of \(G\) if the diameter of \(G – U\) is greater than the diameter of \(G\). In the present work, we first prove that every smallest generalized cutset of Johnson graph \(J(n,k)\) is a local cut except for \(J(4,2)\). Then we show that every smallest diameter-increasing set in \(J(n,k)\) is a subset of a local cut except for \(J(n,2)\) and \(J(6, 3)\).

Let \(G\) be a finite abelian group with exponent \(n\). Let \(s(G)\) denote the smallest integer \(l\) such that every sequence over \(G\) of length at least \(l\) has a zero-sum subsequence of length \(n\). For \(p\)-groups whose exponent is odd and sufficiently large (relative to Davenport’s constant of the group) we obtain an improved upper bound on \(s(G)\), which allows to determine \(s(G)\) precisely in special cases. Our results contain Kemnitz’ conjecture, which was recently proved, as a special case.