For each of the parameter sets \((30, 7, 15)\) and \((26, 12, 55)\), a simple \(3\)-design is given. They have \(\text{PSL}(2, 29)\) and \(\text{PSL}(2, 25)\) as their automorphism group, respectively. Each of the two simple \(3\)-designs is the first one ever known with the parameter set given and \(4\) in each of the two parameter sets is minimal for the given \(v\) and \(k\).

In this paper, we study linear codes over finite chain rings. We relate linear cyclic codes, \((1 + \gamma^k)\)-cyclic codes and \((1 – \gamma^k)\)-cyclic codes over a finite chain ring \(R\), where \(\gamma\) is a fixed generator of the unique maximal ideal of the finite chain ring \(R\), and the nilpotency index of \(\gamma\) is \(k+1\). We also characterize the structure of \((1+\gamma^k)\)-cyclic codes and \((1 – \gamma^k)\)-cyclic codes over finite chain rings.

Let \(G\) be a graph with \(n\) vertices. The mean integrity of \(G\) is defined as follows:\(J(G) = min_{P \subseteq V} \{|P| + \tilde{m}(G – P)\},\) where \(\tilde{m}(G – P) = \frac{1}{n-|P|}\sum_{v \in G – P} n_v\) and \(n_v\) is the size of the component containing \(v\). The main result of this article is a formula for the mean integrity of a path \(P_n\) of \(n\) vertices. A corollary of this formula establishes the mean integrity of a cycle \(C_n\) of \(n\) vertices.

It is known that any reducible additive hereditary graph property has infinitely many minimal forbidden graphs, however the proof of this fact is not constructive. The purpose of this paper is to construct infinite families of minimal forbidden graphs for some classes of reducible properties. The well-known Hajós’ construction is generalized and some of its applications are presented.

In this paper, we prove that for any graph \(G\), there is a dominating induced subgraph which is a cograph. Two new domination parameters \(\gamma_{cd}\) – the cographic domination number and \(\gamma_{gcd}\) – the global cographic domination number are defined. Some properties, including complexity aspects, are discussed.

Given a permutation \(\pi\) chosen uniformly from \(S_n\), we explore the joint distribution of \(\pi(1)\) and the number of descents in \(\pi\). We obtain a formula for the number of permutations with \(Des(\pi) = d\) and \(\pi(1) = k\), and use it to show that if \(Des(\pi)\) is fixed at \(d\), then the expected value of \(\pi(1)\) is \(d+1\). We go on to derive generating functions for the joint distribution, show that it is unimodal if viewed correctly, and show that when \(d\) is small the distribution of \(\pi(1)\) among the permutations with \(d\) descents is approximately geometric. Applications to Stein’s method and the Neggers-Stanley problem are presented.

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

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.

For positive integers \(k \leq n\), the crown \(C_{n,k}\) is the graph with vertex set \(\{a_0, a_1, \ldots, a_{n-1}, b_0, b_1, \ldots, b_{n-1}\}\) and edge set \(\{a_ib_j : 0 \leq i \leq n-1, j = i+1, i+2, \ldots, i+k \pmod{n}\}\). A caterpillar is a tree of order at least three which contains a path such that each vertex not on the path is adjacent to a vertex on the path. Being a connected bipartite graph, a caterpillar is balanced if the two parts of the bipartition of its vertices have equal size; otherwise, it is unbalanced. In this paper, we obtain the necessary and sufficient condition for balanced-caterpillar factorization of crowns. The criterion for unbalanced-caterpillar factorization of crowns is open. We also obtain the necessary and sufficient condition for directed caterpillar factorization of symmetric crowns.

This paper determines that the connectivity of the Cartesian product \(G_1 \square G_2\) of two graphs \(G_1\) and \(G_2\) is equal to \(\min\{\kappa_1v_2 + \kappa_2v_1, \delta_1 + \delta_2 \}\), where \(v_i, \kappa_i\), and \(\delta_i\) are the order, connectivity, and minimum degree of \(G_i\), respectively, for \(i = 1, 2\). Additionally, some necessary and sufficient conditions are given for \(G_1 \square G_2\) to be maximally connected and super-connected.

This paper deals with two types of graph labelings namely, super \((a, d)\)-edge antimagic total labeling and \((a, d)\)-vertex antimagic total labeling. We provide super \((a, d)\)-edge antimagic total labeling for disjoint unions of Harary graphs and disjoint unions of cycles. We also provide \((a,d)\)-vertex antimagic total labeling for disjoint unions of Harary graphs, disjoint unions of cycles, sun graphs and disjoint unions of sun graphs,

The existence question for a \(3\)-\((16,7,5)\) design is open, In this paper, we examine possible automorphisms of this design. We consider a minimum subset of basic permutations consisting of cycles of prime length \(p\) and prove that if a \(3\)-\((16,7,5)\) design exists, then it is either rigid or admits basic automorphisms with cycles of length \(2\) or \(3\).

We define a product summation of ordered partition \(f_j(n,m,r) = \sum{c_1^r c_2^r \ldots c_j^rc_{j+1} \ldots c_m}\), where the sum is over all positive integers \(c_1, c_2, \ldots, c_m\) with \(c_1 + c_2 + \cdots + c_m = n\) and \(0 \leq j \leq m\). We concentrate on \(f_m(n,m,r)\) in this paper. The main results are as follows:

(1) The generating function for \(f_m(n,m,r)\) and the explicit formula for \(f_m(n,m,2) , f_m(n,m,3)\) and \(f_m(n,m, 4)\) are obtained.

(2) The relationship between \(f_j(n,m,r)\) for \(r = 2,3\) and the Fibonacci and Lucas numbers is found.

It is shown that for \(2 \leq t \leq n-3\), a strict \(t\)-SB\((n,n-1)\) design does not exist, but for \(n \geq 3\), a non-strict \(2\)-SB\((n,n-1)\) design exists. The concept of large sets for Steiner triple systems is extended to SB designs and examples of large sets for SB designs are given.

It is shown that every well-defined solution to the second-order difference equation in the title, when \((A_n)_{n \in 0}\) is a two-periodic sequence such that \(\max\{A_0, A_1\} \geq 0\), is eventually periodic with period two. In the case \(\max\{A_0, A_1\} \leq 0\), it is shown the existence of unbounded solutions, by describing all solutions in terms of \(A_0\), \(A_1\), \(x_{-1}\), and \(x_0\).

This paper considers the folded hypercube \(FQ_n\) as an enhancement on the hypercube, and obtains some algebraic properties of \(FQ_n\). Using these properties, the authors show that for any two vertices \(x\) and \(y\) in \(FQ_n\), with distance \(d\) and any integers \(h \in \{d, n+1- d\}\) and \(l\) with \(h \leq l \leq 2^n – 1\), \(FQ_n\) contains an \(xy\)-path of length \(l\) and no \(xy\)-path of other length, provided that \(l\) and \(h\) have the same parity.

Let \(G\) be a \(2\)-tough graph on at least five vertices and let \(e_1, e_2\) be a pair of arbitrarily given edges of \(G\). Then
(a) There exists a \(2\)-factor in G containing \(e_1, e_2\).
(b) There exists a \(2\)-factor in G avoiding \(e_1, e_2\).
(c) There exists a \(2\)-factor in G containing \(e_1\) and avoiding \(e_2\).

In this paper, a sufficient condition is obtained for the global asymptotic stability of the following system of difference equations
\[x_{n+1} = \frac{x_ny_{n-1}}{x_ny_{n-1}+1} ,y_{n+1}=\frac{y_n x_{n-1}}{y_nx_{n-1} + 1} , \quad n = 0, 1, 2, \ldots,\]
where the initial values \((x_k, y_k) \in (0, \infty) (\text{for} k=-1,0)\).

Erdős and Sós conjectured in \(1962\) that if the average degree of a graph \(G\) exceeds \(k – 2\), then \(G\) contains every tree on \(k\) vertices. Results from Sauer and Spencer (and independent results from Zhou) prove the special case where \(G\) has \(k\) vertices. Results from Slater, Teo, and Yap prove the case where \(G\) has \(k + 1\) vertices. In \(1996\), Woźniak proved the case where \(G\) has \(k + 2\) vertices. We prove the conjecture for the case where \(G\) has \(k + 3\) vertices.

A semi-double graph is a connected multi-graph such 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. Via the degree-sum of nonadjacent vertices, the up-embeddability of semi-double graphs and single-petal graphs are discussed in this paper. And the results obtained in this paper can be extended to determine the up-embeddability of multi-graphs and pseudographs.

The commuting graph of an arbitrary ring \(R\), denoted by \(\Gamma(R)\), is the graph whose vertices are all non-central elements of \(R\), and two distinct vertices \(a\) and \(b\) are adjacent if and only if \(ab = ba\). In this paper, we investigate the connectivity, the diameter, the maximum degree and the minimum degree of the commuting graph of the quaternion algebra \(\mathbb{Z}_n[i, j, k]\).

A set \(D\) of vertices of a graph \(G = (V, E)\) is a \(\textit{dominating set}\) if every vertex of \(V-D\) is adjacent to at least one vertex in \(D\). The \(\textit{domination number}\) \(\gamma(G)\) is the minimum cardinality of a dominating set of \(G\). A subset of \(V-D\), which is also a dominating set of \(G\), is called an \(\textit{averse dominating set}\) of \(G\) with respect to \(D\). The \(\textit{inverse domination number}\) \(\gamma'(G)\) equals the minimum cardinality of an inverse dominating set \(D\). In this paper, we study classes of graphs whose domination and inverse domination numbers are equal.

A strongly connected digraph \(\Gamma\) is said to be walk regular if for any nonnegative integer \(l\) and any vertex \(u\) of \(\Gamma\), the number of circuits of length \(l\) containing \(u\) depends only on \(l\). This family of digraphs is a directed version of walk regular graphs. In this paper, we discuss some basic properties of walk regular digraphs.

For any \(n \geq 2\) we let \(S_n\) be the set of permutations of the set \(\{1,2,\ldots,n\}\). A reduction \(\overline{f}\) on \(S_n\) is a set of functions \(\{f_i : 1 \leq i \leq n\}\) such that \(f_n\) is the identity function on \(\{1,2,\ldots,n-1\}\) and for \(i n_0\), such that \(\phi(n) \leq n\) for all \(n \geq n_0\), and for which \(p \downarrow \phi(n) \downarrow i = p \downarrow i \downarrow n-1\) for all \(n > n_0\), for all \(i \leq n-1\) and for all \(p \in S_n\). And the system is said to be amenable if for every \(n > n_0\) there is an integer \(k < n\) such that, for all \(p \in S_n\), \(p \downarrow k \downarrow n-1 = p \downarrow n-1\). The purpose of this paper is to study faithful reductions and linked reduction systems. We characterize amenable, linked reduction systems by means of two types of liftings by which a reduction on \(S_{n+1}\) can be formed from one on \(S_n\). And we obtain conditions for a reduction system to be faithful. One interesting consequence is that any amenable, linked reduction system which begins with a simple reduction is faithful.

Let \(N\) be a positive integer and let \(\lambda = (\lambda_1, \lambda_2, \ldots, \lambda_l)\) be a partition of \(N\) of length \(l\), i.e., \(\sum_{i=1}^{l}\lambda_i = N\) with parts \(\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_l \geq 1\). Define \(T(\lambda)\) as the partition of \(N\) with parts \(l\), \(\lambda_1 – 1, \lambda_2 – 1, \ldots, \lambda_l – 1\), ignoring any zeros that might occur. Starting with a partition \(\lambda\) of \(N\), we describe Bulgarian Solitaire by repeatedly applying the shift operation \(T\) to obtain the sequence of partitions

\[\lambda, T(\lambda), T^2(\lambda), \ldots\]

We say a partition \(\mathcal{A}\) of \(N\) is \(T\)-cyclic if \(T^i(\mu) = \mu\) for some \(i \geq 1\). Brandt \([2]\) characterized all \(T\)-cyclic partitions for Bulgarian Solitaire. In this paper, we give an inductive proof of Brandt’s result.

Let \(D\) be an acyclic digraph. The competition graph of \(D\) is a graph which has the same vertex set as \(D\) and has an edge between \(x\) and \(y\) if and only if there exists a vertex \(v\) in \(D\) such that \((x, v)\) and \((y, v)\) are arcs of \(D\). For any graph \(G\), \(G\) together with sufficiently many isolated vertices is the competition graph of some acyclic digraph. The competition number \(k(G)\) of \(G\) is the smallest number of such isolated vertices.
A hole of a graph is a cycle of length at least \(4\) as an induced subgraph. In \(2005\), Kim \([5]\) conjectured that the competition number of a graph with \(h\) holes is at most \(h + 1\). Though Li and Chang \([8]\) and Kim et al. \([7]\) showed that her conjecture is true when the holes do not overlap much, it still remains open for the case where the holes share edges in an arbitrary way. In order to share an edge, a graph must have at least two holes and so it is natural to start with a graph with exactly two holes. In this paper, the conjecture is proved true for such a graph.

Let \(G\) be a graph with domination number \(\gamma(G)\). A dominating set \(S \subseteq V(G)\) has property \(\mathcal{UK}\) if all components of the subgraph it induces in \(G\) are complete. The union of complete graphs domination number of a graph \(G\), denoted \(\gamma_{uk}(G)\), is the minimum possible size of a dominating set of \(G\), which has property \(\mathcal{UK}\). Results on changing and unchanging of \(\gamma_{uk}(G)\) after vertex removal are presented. Also forbidden subgraph conditions sufficient to imply \(\gamma(G) = \gamma_{uk}(G)\) are given.

In this paper, we use the finite Heine \({}_{2}\Phi_1\) transformations given in \([4]\) and some elementary simplifications to obtain several Rogers-Ramanujan type identities.

Using lines in a two-dimensional vector space \({GF}(q^2)\) over \({GF}(q)\), we construct some classes of external difference families over \({GF}(q^2)\).

A digraph \(D\) is a local out-tournament if the outset of every vertex is a tournament. Here, we use local out-tournaments, whose strong components are upset tournaments, to explore the corresponding ranks of the adjacency matrices. Of specific interest is the out-tournament whose adjacency matrix has boolean, nonnegative integer, term, and real rank all equal to the number of vertices, \(n\). Corresponding results for biclique covers and partitions of the digraph are provided.