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.

Let \(\mathcal{D}\) be a \(2\)-\((v,k,4)\) symmetric design, and \(G\) be a subgroup of the full automorphism group of \(\mathcal{D}\). In this paper, we prove that if \(G \leq {Aut}(\mathcal{D})\) is flag-transitive, point-primitive then \(G\) is of affine or almost simple type. We prove further that if a nontrivial \(2\)-\((v, k, 4)\) symmetric design has a flag-transitive, point-primitive, almost simple automorphism group \(G\), then \(\text{Soc}(G)\) is not a sporadic simple group.

We prove explicit formulas for the rank polynomial and Whitney numbers of the distributive lattice of order ideals of the garland poset, ordered by inclusion.

A semi-double graph is such a connected multi-graph that each multi-edge consists of two edges. If there is at most one loop at each vertex of a semi-double graph, then this graph is called a single-petal graph. In this paper, we obtained that if \(G\) is a connected (resp. \(2\)-edge-connected, \(3\)-edge-connected) simple graph of order \(n\), then \(G\) is upper embeddable if \(d_G(u) + d_G(v) \geq \left\lceil\frac{2n-3}{2}\right\rceil\) (resp. \(d_G(u) + d_G(v) \geq \left\lceil\frac{2n-2}{3}\right\rceil, d_G(u) + d_G(v) \geq \left\lceil\frac{2n-23}{2}\right\rceil\)) for any two adjacent vertices \(u\) and \(v\) of \(G\). In addition, by means of semi-double graph and single-petal graph, the upper embeddability of multi-graph and pseudograph are also discussed in this paper.

Let \(d(n, k)\) denote the number of derangements (permutations without fixed points) with \(k\) cycles of the set \([n] = \{1, 2, \ldots, n\}\). In this paper, a new explicit expression for \(d(n, k)\) is presented by graph theoretic method, and a concise regular binary tree representation for \(d(n, k)\) is provided.

This paper devotes to the investigation of \(3\)-designs admitting the special projective linear group \(\text{PSL}(2,q)\) as an automorphism group. When \(q \equiv 3 \pmod{4}\), we determine all the possible values of \(\lambda\) in the simple \(3\)-\((q+1, 7, \lambda)\) designs admitting \(\text{PSL}(2,q)\) as an automorphism group.

We give an optimal degree condition for a tripartite graph to have a spanning subgraph consisting of complete graphs of order \(3\). This result is used to give an upper bound of \(2\Delta\) for the strong chromatic number of \(n\) vertex graphs with \(\Delta \geq n/6\).

A partial Latin square \(P\) of order \(n\) is an \(n \times n\) array with entries from the set \(\{1, 2, \ldots, n\}\) such that each symbol is used at most once in each row and at most once in each column. If every cell of the array is filled, we call \(P\) a Latin square. A partial Latin square \(P\) of order \(n\) is said to be avoidable if there exists a Latin square \(L\) of order \(n\) such that \(P\) and \(L\) are disjoint. That is, corresponding cells of \(P\) and \(L\) contain different entries. In this note, we show that, with the trivial exception of the Latin square of order \(1\), every partial Latin square of order congruent to \(1\) modulo \(4\) is avoidable.