In this paper, we give a complete solution to the existence of lattice group divisible \(3\)-designs with block sizes four and six.

Let \( R \) be a commutative ring with identity and \( \mathbb{A}^*(R) \) be the set of non-zero ideals with non-zero annihilators. The annihilating-ideal graph of \( R \) is defined as the graph \( \mathbb{AG}(R) \) with the vertex set \( \mathbb{A}^*(R) \) and two distinct vertices \( I_1 \) and \( I_2 \) are adjacent if and only if \( I_1 I_2 = (0) \). In this paper, we study some connections between the graph-theoretic properties of \( \mathbb{AG}(R) \) and algebraic properties of the commutative ring \( R \).

Let \( A_n = (a_1, a_2, \ldots, a_n) \) and \( B_n = (b_1, b_2, \ldots, b_n) \) be two sequences of nonnegative integers satisfying \( a_1 \geq a_2 \geq \cdots \geq a_n \), \( a_i \leq b_i \) for \( i = 1,2,\ldots,n \), and \( a_i = a_{i+1} \) implies that \( b_i \geq b_{i+1} \) for \( i = 1,2,\ldots,n-1 \). Let \( I \) be a subset of \( \{1,2,\ldots,n\} \) and \( a_i \equiv b_i \pmod{2} \) for each \( i \in I \). \( (A_n; B_n) \) is said to be partial parity graphic with respect to \( I \) if there exists a simple graph \( G \) with vertices \( v_1, v_2, \ldots, v_n \), such that \( a_i \leq d_G(v_i) \leq b_i \) for \( i = 1,2,\ldots,n \) and \( d_G(v_i) \equiv b_i \pmod{2} \) for each \( i \in I \). In this paper, we give a characterization for \( (A_n; B_n) \) to be partial parity graphic. This is a variation of the partial parity \( (g, f) \)-factor theorem due to Kano and Matsuda in degree sequences.

It’s well known that all of the pooling designs constructed are based on a finite set or a finite vector space. In this paper, we construct two families of pooling designs not only based on finite sets (resp. finite vector spaces) but also on partial mappings (resp. partial linear mappings), and discuss their error-tolerance properties.

Let \( 2^{[m]} \) be ordered by set inclusion, and let \( \mathcal{B} \subseteq 2^{[m]} \) be an antichain. An antichain \( \mathcal{B} \) is called \( k \)-regular (\( k \in \mathbb{N} \)) if for each \( i \in [m] \) there are exactly \( k \) blocks \( B_1, B_2, \ldots, B_k \in \mathcal{B} \) containing \( i \). An antichain is called flat if there exists a positive integer \( l \) such that \( l \leq |B| \leq l+1 \) for all \( B \in \mathcal{B} \), and we call an antichain maximal if the collection of sets \( \mathcal{B} \cup \{B\} \) is not an antichain for all \( B \notin \mathcal{B} \). We call a maximal \( k \)-regular antichain \( \mathcal{B} \subseteq \binom{[m]}{2} \cup \binom{[m]}{3} \) a \( (k,m) \)-MFRAC. In this paper we analyze \( (k,m) \)-MFRACs in the cases \( m \leq 7 \), \( k = m \), \( k = m-1 \), and \( k = m-2 \). We provide some constructions, give necessary conditions for existence, and mention some open problems.

Generalized binomial coefficients are considered. The aim of this paper is to provide a new general combinatorial interpretation of the Lucas-nomial and \( (p,q) \)-nomial coefficients in terms of tiling of \( d \)-dimensional rectangular boxes. The recurrence relation of these numbers is proved in a combinatorial way. To this end, our results are extended to the case of corresponding multi-nomial coefficients.

In this paper, we determine the necessary and sufficient conditions for the existence of simple incomplete triple systems for all \( \lambda \leq 6 \).

Dudeney’s round table problem asks for a set of Hamilton cycles in \( K_n \), having the property that each \( 2 \)-path in \( K_n \) lies in exactly one of the cycles. In this paper, we show how to construct a solution of Dudeney’s round table problem for even \( n \) from a semi-antipodal Hamilton decomposition of \( K_{n-1} \).

Using the spectral invariants of graphs, we present sufficient conditions for some stable properties of graphs.

A matching \( M \) in a graph \( G \) is a subset of \( E(G) \) in which no two edges have a vertex in common. A vertex \( V \) is unsaturated by \( M \) if there is no edge of \( M \) incident with \( V \). A matching \( M \) is called a perfect matching if there is no vertex of the graph that is unsaturated by \( M \). Let \( G \) be a \( k \)-edge-connected graph, \( k \geq 1 \), on even \( n \) vertices, with minimum degree \( r \) and maximum degree \( r + e \), \( e \geq 1 \). In this paper, we find a lower bound for \( n \) when \( G \) has no perfect matchings.

Two kinds of authentication schemes are constructed using singular symplectic geometry over finite fields in this paper. One is an authentication code with arbitration, another is a multi-receiver authentication code. The parameters of two kinds of codes have been computed. Under the assumption that the encoding rules of the transmitter and the receiver are chosen according to a uniform probability distribution, the maximum probabilities of success of different types of deception attacks are also computed.

If \( G_1 \) and \( G_2 \) are two graphs, then the edge amalgamation \( G_1 *_e G_2 \) is defined to be the graph obtained by identifying some given edge of \( G_1 \) with some given edge of \( G_2 \). In this paper, it is shown that \( \gamma(G_1 *_e G_2 *_e \ldots *_e G_n) = \lceil \frac{n}{2} \rceil \) where \( G_i \) (\( 1 \leq i \leq n \)) is a critical graph of minimum genus \( 1 \).

A set \( S \subseteq V \) is a dominating set of a graph \( G = (V, E) \) if each vertex in \( V \) is either in \( S \) or is adjacent to a vertex in \( S \). A vertex is said to dominate itself and all its neighbors. A set \( S \subseteq V \) is a \emph{total dominating set} of a graph \( G = (V, E) \) if each vertex in \( V \) is adjacent to a vertex in \( S \). In total domination, a vertex no longer dominates itself. These two types of domination can be thought of as representing the vertex set of a graph as the union of the closed (domination) and open (total domination) neighborhoods of the vertices in the set \( S \). A set \( S \subseteq V \) is a \emph{total, efficient dominating set} (also known as an \emph{efficient open dominating set}) of a graph \( G = (V, E) \) if each vertex in \( V \) is adjacent to exactly one vertex in \( S \). In 2002, Gavlas and Schultz completely classified all cycle graphs that admit a total, efficient dominating set. This paper extends their result to two classes of Cayley graphs.

Seymour’s Second Neighborhood Conjecture claims that every simple digraph has a vertex whose first neighborhood is at most as large as its second neighborhood. We confirm this conjecture for neighbor-connection free simple digraphs and distance-two simple digraphs. As a consequence, the conjecture is true for triangle-free digraphs and \(4\)-cycle free digraphs.

We consider the random process arising from a sequence of random Seidel switching operations on \( n \) vertices. We show that this process can be interpreted as a random walk on a Cayley graph of an abelian group, and use spectral methods to show that the random process converges to a stationary distribution in \( O(n \log(n)) \) steps. We then consider two generalizations: we allow multiple states for each edge, and restrict the process to a fixed host graph \( H \). We then analyze the general case and obtain convergence results for any graph \( H \).

In this paper, we present the study of the interlace polynomials for \( n \)-claw graphs. For a positive integer \( n > 1 \), an \( n \)-claw graph \( W_n \) is a tree that has one center vertex and \( n \) claws. The center vertex is connected to one vertex of each of the \( n \) claws using one edge of the claw. We present iterative formulas and explicit formulas for the interlace polynomial of \( W_n \). Furthermore, some interesting properties of the polynomial are discussed.

Bar visibility graphs (BVG) are graphs whose vertices can be assigned disjoint horizontal line segments in the plane so that adjacent vertices correspond to pairs of bars that are visible to each other via an unobstructed, vertical band of visibility. A \( k \)-stack layout of a graph is a linear vertex ordering and a \( k \)-edge coloring such that each color class avoids crossing edges with respect to the linear order. BVGs and stack layouts were introduced separately in the 1970s and have many applications including testing circuit boards, VLSI design, and graph drawing. Motivated by applications to carousel navigation design, we introduce a hybrid class of graphs called unit stack visibility graphs and give a combinatorial characterization of these graphs. We leave open the problem of determining whether a polynomial-time algorithm exists to recognize unit stack visibility graphs.

Two quasigroup identities of importance in combinatorics, Schröder’s Second Law and Stein’s Third Law, share many common features that are incorporated under the guise of palindromic quasigroups. A graph-theoretical technique yields a topological proof for the congruence restrictions on the spectrum of Schröder or outer palindromic quasigroups. The potential for a comparable proof applicable to Stein or inner palindromic quasigroups raises open graph-theoretical and combinatorial problems. Imposition of extra Sudoku-like conditions on Latin squares of square order, based on the coloring of so-called Sudoku graphs, leads to the concept of a Sudoku quasigroup. It is shown that the spectrum of inner palindromic Sudoku quasigroups comprises every perfect square, thereby identifying the chromatic number of each Sudoku graph.

Hoffman proved that for a simple graph \( G \), the chromatic number \( \chi(G) \) obeys \( \chi(G) \geq 1 – \frac{\lambda_1}{\lambda_n} \), where \( \lambda_1 \) and \( \lambda_n \) are the maximal and minimal eigenvalues of the adjacency matrix of \( G \), respectively. Lovász later showed that \( \chi(G) \geq 1 – \frac{\lambda_1}{\lambda_n} \) for any (perhaps negatively) weighted adjacency matrix.

In this paper, we give a probabilistic proof of Lovász’s theorem, then extend the technique to derive generalizations of Hoffman’s theorem when allowed a certain proportion of edge-conflicts. Using this result, we show that if a \( 3 \)-uniform hypergraph is \( 2 \)-colorable, then \( \bar{d} \leq – \frac{3}{2} \lambda_{\text{min}} \) where \( \bar{d} \) is the average degree and \( \lambda_{\text{min}} \) is the minimal eigenvalue of the underlying graph. We generalize this further for \( k \)-uniform hypergraphs, for the cases \( k = 4 \) and \( 5 \), by considering several variants of the underlying graph.

In 1967, Erdős and Hajnal asked the question: Does there exist a \( K_4 \)-free graph that is not the union of two triangle-free graphs? Finding such a graph involves solving a special case of the classical Ramsey arrowing operation. Folkman proved the existence of these graphs in 1970, and they are now called Folkman graphs. Erdős offered \$100 for deciding if one exists with less than \( 10^{10} \) vertices. This problem remained open until 1988 when Spencer, in a seminal paper using probabilistic techniques, proved the existence of a Folkman graph of order \( 3 \times 10^9 \) (after an erratum), without explicitly constructing it. In 2008, Dudek and Rödl developed a strategy to construct new Folkman graphs by approximating the maximum cut of a related graph, and used it to improve the upper bound to 941. We improve this bound first to 860 using their approximation technique and then further to 786 with the MAX-CUT semidefinite programming relaxation as used in the Goemans-Williamson algorithm.

Let a set \([n] = \{1,2,\ldots,n\}\) be given. Finding a subset \( S \) of \( 2^{[n]} \) with minimum cardinality such that, for any two distinct elements \( x, y \in [n] \), there exist disjoint subsets \( A_x, A_y \in \mathcal{S} \) such that \( x \in A_x \) and \( y \in A_y \) is called the \emph{extremal set} problem. In this paper, we define the Extremal Set Decision (ESD) Problem and study its complexity.

A cyclic base ordering of a connected graph \( G \) is a cyclic ordering of \( E(G) \) such that every \( |V(G)| – 1 \) cyclically consecutive edges form a spanning tree of \( G \). Let \( G \) be a graph with \( E(G) \neq \emptyset \) and let \( \omega(G) \) denote the number of components in \( G \). The invariants \( d(G) \) and \( \gamma(G) \) are respectively defined as \( d(G) = \frac{|E(G)|}{|V(G)| – \omega(G)} \) and \( \gamma(G) = \text{max}\{d(H)\} \), where \( H \) runs over all subgraphs of \( G \) with \( E(H) \neq \emptyset \). A graph \( G \) is uniformly dense if \( d(G) = \gamma(G) \). Kajitani et al. [8] conjectured in 1988 that a connected graph \( G \) has a cyclic base ordering if and only if \( G \) is uniformly dense. In this paper, we show that this conjecture holds for some classes of uniformly dense graphs.

A graph \( G \) is a \((t, r)\)-regular graph if every collection of \( t \) independent vertices is collectively adjacent to exactly \( r \) vertices. Let \( p, s \), and \( m \) be positive integers, where \( m \geq 2 \), and let \( G \) be a \((2, r)\)-regular graph. If \( n \) is sufficiently large, then \( G \) is isomorphic to \( K_s + mK_p \), where \( 2(p-1) + s = r \). A nested \((2, r)\)-regular graph is constructed by replacing selected cliques in a \((2, r)\)-regular graph with a \((2, r’)\)-regular graph and joining the vertices of the peripheral cliques. We examine the network properties such as the average path length, clustering coefficient, and the spectrum of these nested graphs.

Given a graph \( G \), we show how to compute the number of (perfect) matchings in the graphs \( G \Box P_n \) and \( G \Box C_n \), by looking at appropriate entries in a power of a particular matrix. We give some generalizations and extensions of this result, including showing how to compute tilings of \( k \times n \) boards using monomers, dimers, and \( 2 \times 2 \) tiles.

Consider a simple undirected graph \( G = (V, E) \). A family of subtrees, \(\{T_v\}_{v \in V}\), of a tree \(\mathcal{T}\) is called a \((\mathcal{T}; t)\)-representation of \(G\) provided \( uv \in E \) if and only if \( |T_u \cap T_v| \geq t \). In this paper, we consider \((\mathcal{T}; t)\)-representations for graphs containing large asteroidal sets, where \(\mathcal{T}\) is a subdivision of the \(n\)-star \(K_{1, n}\). An asteroidal set in a graph \(G\) is a subset \(A\) of the vertex set such that for all 3-element subsets of \(A\), there exists a path in \(G\) between any two of these vertices which avoids the neighborhood of the third vertex. We construct a representation of an asteroidal set of size \( n + \sum_{k=2}^{n} \binom{n}{k} \binom{t-2}{k-1} \) and show that no graph containing a larger asteroidal set can be represented.