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 \([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 \({signed \; k -dominating\; function}\) of \( G \) if \( \sum_{u \in N_G[v]} f(u) \geq k \) for all \( v \in V \). The \({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 \({signed \;total \; k-dominating \;function}\) and \({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 \({signed \; k -domination \;number}\) is the maximum value of \( \sum_{u \in V} f(u) \) taken over all \({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.

In this paper, some formulae for computing the numbers of spanning trees of the corona and the join of graphs are deduced.

Partially filled \(6 \times 6\) Sudoku grids are categorized based on the arrangement of the values in the first three rows. This categorization is then employed to determine the number of \(6 \times 6\) Sudoku grids.

Stankova and West proved in 2002 that the patterns \( 231 \) and \( 312 \) are shape-Wilf-equivalent. Their proof was nonbijective. We give a new characterization of \( 231 \) and \( 312 \) avoiding full rook placements and use this to give a simple bijection that demonstrates the shape-Wilf-equivalence.