Define \(\mathcal{D}_k\) to be the class of graphs such that, for every independent set \(\{v_1,\ldots,v_h\}\) of vertices with \(2 \leq h \leq k\), if \(S\) is an inclusion-minimal set of vertices whose deletion would put \(v_1,\ldots,v_h\) into \(h\) distinct connected components, then \(S\) induces a complete subgraph; also, let \(\mathcal{D} = \bigcap_{k\geq2} \mathcal{D}_k\). Similarly, define \(\mathcal{D}_k’\) and \(\mathcal{D}’\) with “complete” replaced by “edgeless,” and define \(\mathcal{D}_k^*\) and \(\mathcal{D}^*\) with “complete” replaced by “complete or edgeless.” The class \(\mathcal{D}_2\) is the class of chordal graphs, and the classes \(\mathcal{D}\), \(\mathcal{D}_2’\), and \(\mathcal{D}_2^*\) have also been characterized recently. The present paper gives unified characterizations of all of the classes \(\mathcal{D}_k\), \(\mathcal{D}_k’\), \(\mathcal{D}_k^*\), \(\mathcal{D}\), \(\mathcal{D}’\), and \(\mathcal{D}^*\).

Catalan Numbers and their generalizations are found throughout the field of Combinatorics. This paper describes their connection to numbers whose digits appear in the number’s own \(p^{th}\) root. These are called Grafting Numbers and they are defined by a class of polynomials given by the Grafting Equation: \((x+y)^p = b^ax\). A formula that solves for \(x\) in these polynomials uses a novel extension to Catalan Numbers and will be proved in this paper. This extension results in new sequences that also solve natural extensions to previous Combinatorics problems. In addition, this paper will present computationally verified conjectures about formulas and properties of other solutions to the Grafting Equation.

A \( d \)-angulation of a surface is an embedding of a 3-connected graph on that surface that divides it into \( d \)-gonal faces. A \( d \)-angulation is said to be Grünbaum colorable if its edges can be \( d \)-colored so that every face uses all \( d \) colors. Up to now, the concept of Grünbaum coloring has been related only to triangulations (\( d = 3 \)), but in this note, this concept is generalized for an arbitrary face size \( d \geq 3 \). It is shown that the face 2-colorability of a \( d \)-angulation \( P \) implies the Grünbaum colorability of \( P \). Some wide classes of triangulations have turned out to be face 2-colorable.

Let \( G \) be a claw-free graph of order \( 4k \), where \( k \) is a positive integer. In this paper, it is proved that if the degree sum \( d(u) + d(v) \) is at least \( 4k – 2 \) for every pair of nonadjacent vertices \( u, v \in V(G) \), then \( G \) has a spanning subgraph consisting of \( k – 1 \) quadrilaterals and a 4-path such that all of them are vertex-disjoint, unless \( G \) is isomorphic to \( K_{4k_1 + 2} \cup K_{4k_2 + 2} \), or \( K_{4k_1 + 1} \cup K_{4k_2 + 3} \), where \( k_1 \geq 0, k_2 \geq 0, k_1 + k_2 = k – 1 \). We further showed that the requirement about claw-free is indispensable and the degree condition is sharp.

For \( n \geq 1 \) we call a sequence \( s_1, s_2, \ldots, s_n \) an up-down sequence of length \( n \) when (i) \( s_1 = 1 \); (ii) \( s_i \in \{1, 2, 3, 4\} \), for \( 2 \leq i \leq n \); and, (iii) \( |s_i – s_{i-1}| = 1 \), for \( 2 \leq i \leq n \). We count the number of inversions and coinversions for all such up-down sequences of length \( n \), as well as the sum of the major indices for all these sequences of length \( n \).

Das \([4]\), Feng et al. \([5]\), and Li et al. \([13]\) obtained upper bounds for the number of spanning trees of a connected graph. Using some ideas in \([4]\), \([5]\), and \([13]\) and other established results, we obtain new upper bounds for the number of spanning trees of a connected graph.

Given two non-isomorphic bipartite 2-factors \( F_1 \) and \( F_2 \) of order \( 4n \), the Bipartite Hamilton-Waterloo Problem (BHWP) asks for a 2-factorization of \( K_{2n,2n} \) into \( \alpha \) copies of \( F_1 \) and \( \beta \) copies of \( F_2 \), where \( \alpha + \beta = n \) and \( \alpha, \beta \geq 1 \). We show that the BHWP has a solution when \( F_1 \) is a refinement of \( F_2 \), where no component of \( F_1 \) is a \( C_4 \) or \( C_6 \), except possibly when \( \alpha = 1 \) and either (i) \( F_2 \) is a \( C_4 \)-factor or (ii) \( F_2 \) has more than one \( C_4 \) with all other components of an order \( r \equiv 0 \pmod{4} > 4 \) or (iii) \( F_2 \) has components with an order \( r \equiv 2 \pmod{4} \), when \( n \) is even. We also show that there does not exist a factorization of \( K_{6,6} \) into a single 12-cycle and two \( C_4 \)-factors.

For every integer \( c \), let \( r(2, 2, c) \) be the least integer \( n \) such that for every 2-coloring of the set \( \{1, 2, \ldots, n\} \) there exists a monochromatic solution to the equation \[ 2x_1 + 2x_2 + c = x_3. \]
Secondly, for every integer \( c \), let \( r(2, 2, 2, c) \) be the least integer \( n \) such that for every 2-coloring of the set \( \{1, 2, \ldots, n\} \) there exists a monochromatic solution to the equation \[ 2x_1 + 2x_2 + 2x_3 + c = x_4. \]
In this paper, exact values are found for \( r(2, 2, c) \) and \( r(2, 2, 2, c) \).

We construct a class of maximal partial line spreads in \( \mathrm{PG}(4, q) \), that we call \( q \)-added maximal partial line spreads. We obtain them by depriving a line spread of a hyperplane of some lines and adding \( q+1 \) pairwise skew lines not in the hyperplane for each removed line. We do it in a theoretical way for every value of \( q \), and by a computer search for \( q \leq 16 \). More precisely, we prove that for every \( q \) there are \( q \)-added MPS of size \( q^2 + kq + 1 \), for every integer \( k = 1, \ldots, q-1 \), while by a computer search we get larger cardinalities.

Let \( i(G) \) denote the minimum cardinality of an independent dominating set for \( G \). A graph \( G \) is \( k \)-\( i \)-critical if \( i(G) = k \), but \( i(G + uv) < k \) for any pair of non-adjacent vertices \( u \) and \( v \) of \( G \). In this paper, we show that if \( G \) is a connected \( k \)-\( i \)-critical graph, for \( k \geq 3 \), with a cutvertex \( u \), then the number of components of \( G – u \), \( \omega(G – u) \), is at most \( k – 1 \) and there are at most two non-singleton components. Further, if \( \omega(G – u) = k – 1 \), then a characterization of such graphs is given.