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.