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.