A graph is called induced matching extendable, if every induced matching of it is contained in a perfect matching of it. A graph \(G\) is called \(2k\)-vertex deletable induced matching extendable, if \(G — S\) is induced matching extendable for every \(S \subset V(G)\) with \(|S| = 2k\). The following results are proved in this paper. (1) If \(\kappa(G) \geq \lceil \frac{v(G)}{3} \rceil +1\) and \(\max\{d(u), d(v)\} \geq \frac{2v(G)+1}{3}\) for every two nonadjacent vertices \(u\) and \(v\), then \(G\) is induced matching extendable. (2) If \(\kappa(G) \geq \lceil \frac{v(G)+4k}{3}\rceil\) and \(\max\{d(u), d(v)\} \geq \lceil \frac{2v(G)+2k}{3} \rceil\) for every two nonadjacent vertices \(u\) and \(v\), then \(G\) is \(2k\)-vertex deletable induced matching extendable. (3) If \(d(u) + d(v) \geq 2\lceil\frac{2v(G)+2k}{3} \rceil – 1\) for every two nonadjacent vertices \(u\) and \(v\), then \(G\) is \(2k\)-vertex deletable IM-extendable. Examples are given to show the tightness of all the conditions.

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)\).