An oriented coloring of a directed graph is a vertex coloring in which no two adjacent vertices belong to the same color class and all of the arcs between any two color classes have the same direction. Injective oriented colorings are oriented colorings that satisfy the extra condition that no two in-neighbors of a vertex receive the same color. The oriented chromatic number of an unoriented graph is the maximum oriented chromatic number over all possible orientations. Similarly, the injective oriented chromatic number of an unoriented graph is the maximum injective oriented chromatic number over all possible orientations. The main results obtained in this paper are bounds on the injective oriented chromatic number of two-dimensional grid graphs.

Let \(\lambda K_{v}\) be the complete multigraph of order \(v\) and index \(\lambda\), where any two distinct vertices \(x\) and \(y\) are joined exactly by \(\lambda\) edges \(\{x,y\}\). Let \(G\) be a finite simple graph. A \(G\)-design of \(\lambda K_{v}\), denoted by \((v, G, \lambda)\)-GD, is a pair \((X, \mathcal{B})\), where \(X\) is the vertex set of \(K_v\) and \(\mathcal{B}\) is a collection of subgraphs of \(K_{v}\), called blocks, such that each block is isomorphic to \(G\) and any two distinct vertices in \(K_{v}\) are joined in exactly \(\lambda\) blocks of \(\mathcal{B}\). There are four graphs with seven vertices, seven edges, and one 5-cycle, denoted by \(G_i\), \(i=1,2,3,4\). In \cite{9}, we have solved the existence problems of \((v, G_i, 1)\)-GD. In this paper, we obtain the existence spectrum of \((v, G_i, \lambda)\)-GD for any index \(\lambda\).

The values of the Ramsey numbers \( R(C_4, H) \), for any graph \( H \) on 6 vertices, are shown in [3]. An erratum is corrected in [4,6], giving \( R(C_4, K_{3,3}) = 11 \).

In this paper, we correct three other errata of [3], proving that \( R(C_4, K_1 + (K_{2,3} – e)) = 9 \), \( R(C_4, \overline{K_3 \cup P_3}) = 11 \), and \( R(C_4, \overline{2P_3}) = 11 \), instead of 10.

We use dynamic programming to compute the domination number of the Cartesian product of two directed paths, \( \overrightarrow{P}_m \) and \( \overrightarrow{P}_n \), for \( m \leq 25 \) and all \( n \). This suggests that the domination number for \(\min(m,n) \geq 4\) is \( \left\lfloor \frac{(m+1)(n+1)}{3} \right\rfloor – 1 \), which we then confirm by showing that this is both an upper and a lower bound on the domination number.

In 1975, Erdős proposed the problem of determining the maximal number of edges in a graph on \( n \) vertices that contains no triangles or squares. In this paper, we consider a generalized version of the problem, i.e., what is the maximum size, \( ex(n; t) \), of a graph of order \( n \) and girth at least \( t+1 \) (containing no cycles of length less than \( t+1 \)). The set of those extremal \( C_t \)-free graphs is denoted by \( EX(n; t) \). We consider the problem on special types of graphs, such as pseudotrees, cacti, graphs lying in a square grid, Halin, generalized Halin, and planar graphs. We give the extremal cases, some constructions, and we use these results to obtain general lower bounds for the problem in the general case.

This paper develops the polyhedral approach to integer partitions. We consider the set of partitions of an integer \( n \) as a polytope \( P_n \subset \mathbb{R}^n \). Vertices of \( P_n \) form the class of partitions that provide the first basis for the whole set of partitions of \( n \). Moreover, we show that there exists a subclass of vertices, from which all others can be generated with the use of two combinatorial operations. The calculation demonstrates a considerable decrease in the cardinality of these classes of basic partitions as \( n \) grows. We focus on the vertex enumeration problem for \( P_n \). We prove that vertices of all partition polytopes form a partition ideal of the Andrews partition lattice. This allows us to construct vertices of \( P_n \) by a lifting method, which requires examining only certain partitions of \( n \). A criterion of whether a given partition is a convex combination of two others connects vertices with knapsack partitions, sum-free sets, Sidon sets, and Sidon multisets introduced in the paper. All but a few non-vertices for small \( n \)’s were recognized with its help. We also prove several easy-to-check necessary conditions for a partition to be a vertex.

Like the Coxeter graph becoming reattached into the Klein graph in [3], the Levi graphs of the \(9_3\) and \(10_3\) self-dual configurations, known as the Pappus and Desargues (\(k\)-transitive) graphs \(\mathcal{P}\) and \(\mathcal{D}\) (where \(k = 3\)), also admit reattachments of the distance-(\(k – 1\)) graphs of half of their oriented shortest cycles via orientation assignments on their common (\(k – 1\))-arcs, concurrent for \(\mathcal{P}\) and opposite for \(\mathcal{D}\), now into 2 disjoint copies of their corresponding Menger graphs. Here, \(\mathcal{P}\) is the unique cubic distance-transitive (or CDT) graph with the concurrent-reattachment behavior while \(\mathcal{D}\) is one of 7 CDT graphs with the opposite-reattachment behavior, including the Coxeter graph. Thus, \(\mathcal{P}\) and \(\mathcal{D}\) confront each other in these respects, obtained via \(\mathcal{C}\)-ultrahomogeneous graph techniques \cite{4,5} that allow us to characterize the obtained reattachment Menger graphs in the same terms.

Let \( k \) be a positive integer and \( G = (V, E) \) be a graph of minimum degree at least \( k – 1 \). A function \( f: V \to \{-1, 1\} \) is called a \emph{signed \( k \)-dominating function} of \( G \) if \( \sum_{u \in N_G[v]} f(u) \geq k \) for all \( v \in V \). The \emph{signed \( k \)-domination number} of \( G \) is the minimum value of \( \sum_{v \in V} f(v) \) taken over all signed \( k \)-dominating functions of \( G \). The \emph{signed total \( k \)-dominating function} and \emph{signed total \( k \)-domination number} of \( G \) can be similarly defined by changing the closed neighborhood \( N_G[v] \) to the open neighborhood \( N_G(v) \) in the definition. The upper \emph{signed \( k \)-domination number} is the maximum value of \( \sum_{u \in V} f(u) \) taken over all \emph{minimal} signed \( k \)-dominating functions of \( G \). In this paper, we study these graph parameters from both algorithmic complexity and graph-theoretic perspectives. We prove that for every fixed \( k \geq 1 \), the problems of computing these three parameters are all \( \mathcal{NP} \)-hard. We also present sharp lower bounds on the signed \( k \)-domination number and signed total \( k \)-domination number for general graphs in terms of their minimum and maximum degrees, generalizing several known results about signed domination.

In this paper, we study a pair of simplicial complexes, which we denote by \( \mathcal{B}(k,d) \) and \( \mathcal{ST}(k+1,d-k-1) \), for all nonnegative integers \( k \) and \( d \) with \( 0 \leq k \leq d-2 \). We conjecture that their underlying topological spaces \( |\mathcal{B}(k,d)| \) and \( |\mathcal{ST}(k+1,d-k-1)| \) are homeomorphic for all such \( k \) and \( d \). We answer this question when \( k = d-2 \) by relating the complexes through a series of well-studied combinatorial operations that transform a combinatorial manifold while preserving its PL-homeomorphism type.

Let \( D = (V,A) \) be a finite and simple digraph. A Roman dominating function (RDF) on \( D \) is a labeling \( f: V(D) \to \{0,1,2\} \) such that every vertex \( v \) with label \( 0 \) has a vertex \( w \) with label \( 2 \) such that \( wv \) is an arc in \( D \). The weight of an RDF \( f \) is the value \( \omega(f) = \sum_{v \in V} f(v) \). The Roman domination number of a digraph \( D \), denoted by \( \gamma_R(D) \), equals the minimum weight of an RDF on \( D \). The Roman reinforcement number \( r_R(D) \) of a digraph \( D \) is the minimum number of arcs that must be added to \( D \) in order to decrease the Roman domination number. In this paper, we initiate the study of Roman reinforcement number in digraphs and we present some sharp bounds for \( r_R(D) \). In particular, we determine the Roman reinforcement number of some classes of digraphs.