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^{a}x$. 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\ge 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\ge 0,k_2\ge 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\ge 1$ we call a sequence $s_1,s_2,\dots ,s_n$ an up-down sequence of length $n$ when (i) $s_1=1$; (ii) $s_i\in \{1,2,3,4\}$, for $2\le i\le n$; and, (iii) $|s_i–s_{i-1}|=1$, for $2\le i\le 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 \ge 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(\mathrm{mod}4)>4$ or (iii) $F_2$ has components with an order $r\equiv 2(\mathrm{mod}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,\dots ,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,\dots ,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{P}\mathrm{G}(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\le 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,\dots ,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\ge 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.

For a nontrivial connected graph $G$, let $c:V(G)\to {\mathbb{Z}}_2$ be a vertex coloring of $G$ where $c(v)\ne 0$ for at least one vertex $v$ of $G$. Then the coloring $c$ induces a new coloring $\sigma :V(G)\to {\mathbb{Z}}_2$ defined by $\sigma (v)=\sum _{u\in N[v]}c(u)$, where $N[v]$ is the closed neighborhood of $v$ and addition is performed in ${\mathbb{Z}}_2$. If $\sigma (v)=0\in {\mathbb{Z}}_2$ for every vertex $v$ in $G$, then the coloring $c$ is called a modular monochromatic $(2,0)$-coloring of $G$. A graph $G$ having a modular monochromatic $(2,0)$-coloring is a monochromatic $(2,0)$-colorable graph. The minimum number of vertices colored 1 in a modular monochromatic $(2,0)$-coloring of $G$ is the $(2,0)$-chromatic number ${\chi }_{(2,0)}(G)$ of $G$. A monochromatic $(2,0)$-colorable graph $G$ of order $n$ is $(2,0)$-extremal if ${\chi }_{(2,0)}(G)=n$. It is known that a tree $T$ is $(2,0)$-extremal if and only if every vertex of $T$ has odd degree. In this work, we characterize all trees of order $n$ having $(2,0)$-chromatic number $n-1$, $n-2$, or $n-3$, and investigate the structures of connected graphs having large $(2,0)$-chromatic numbers.

A seed of a word $x$ is a cover of a superword of $x$. In this paper, we study the frequency of appearance of seeds in words. We give bounds for the average number of seeds in a word and we investigate the maximum number of distinct seeds that can appear in a word. More precisely, we prove that a word has $O(n)$ seeds on average and that the maximum number of distinct seeds in a word is between $\frac{1}{6}(n^2)+o(n^2)$ and $\frac{1}{4}(n^2)+o(n^2)$, and we reveal some properties of an extremal word for the last case.

Self-dual $1$-configurations $(n_d{)}_1$ have the most $K_d$-separated Menger graph $\mathcal{Y}$ for connected self-dual configurations $(n_d)$. Such $\mathcal{Y}$ is most symmetric if it is $K_d$-ultrahomogeneous. In this work, such a graph $\mathcal{Y}$ is presented for $(n,d)=(102,4)$ and shown to relate $n$ copies of the cuboctahedral graph $L(Q_3)$ to the $n$ copies of $K_4$. These are shown to share each copy of $K_3$ with two copies of $L(Q_3)$. Vertices and copies of $L(Q_3)$ in $\mathcal{Y}$ are the points and lines of a self-dual $({104}_{12}{)}_1$.

A Roman dominating function (RDF) on a graph $G$ is a function $f:V(G)\to \{0,1,2\}$ satisfying the condition that every vertex $u$ with $f(u)=0$ is adjacent to at least one vertex $v$ for which $f(v)=2$. The weight of a Roman dominating function is the value $f(V(G))=\sum _{u\in V(G)}f(u)$. The Roman domination number, ${\gamma }_R(G)$, of $G$ is the minimum weight of a Roman dominating function on $G$. An RDF $f$ is called an independent Roman dominating function if the set of vertices assigned non-zero values is independent. The independent Roman domination number, $i_R(G)$, of $G$ is the minimum weight of an independent RDF on $G$. In this paper, we improve previous bounds on the independent Roman domination number of a graph.

It has been conjectured that the edge domination number of the $m\times n$ grid graph, denoted by ${\gamma }^{\prime }(P_m\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{P}_n)$, is $\lceil mn/3\rceil$ when $m,n\ge 2$. Our main result gives support for this conjecture by proving that $\lceil mn/3\rceil \le {\gamma }^{\prime }(P_m\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{P}_n)\le mn/3+n/12+1$, when $m,n\ge 2$. We furthermore show that the conjecture holds when $mn$ is a multiple of three and also when $m\le 13$. Despite this support for the conjecture, our proofs lead us to believe that the conjecture may be false when $m$ and $n$ are large enough and $mn$ is not a multiple of three. We state a new conjecture for the values of ${\gamma }^{\prime }(P_m\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{P}_n)$.

In this paper, we present some patterns related to derangements. We find the distribution of the ${\delta }^{\prime }$-transformation applied to all unicyclic derangements of order $n$, and the distribution of the ${\delta }^{\prime }$-transformation applied to all derangements of order $n$, considered in one-line notation. We introduce the notion of a matrix of forbidden pairs that helps us in solving our problems. We also give and prove a theorem related to derangements.

We present a new type of tournament design that we call a complete mixed doubles round robin tournament, $\text{CMDRR}(n,k)$, that generalizes spouse-avoiding mixed doubles round robin tournaments and strict Mitchell mixed doubles round robin tournaments. We show that $\text{CMDRR}(n,k)$ exist for all allowed values of $n$ and $k$ apart from 4 exceptions and 31 possible exceptions. We show that a fully resolvable $\text{CMDRR}(2n,0)$ exists for all $n\ge 5$ and a fully resolvable $\text{CMDRR}(3n,n)$ exists for all $n\ge 5$ and $n$ odd. We prove a product theorem for constructing $\text{CMDRR}(n,k)$.

Recently introduced invariants, copoint pre-hull number and convex pre-hull number, are both numerical measures of nonconvexity of a graph $G$ that is a convex space. We consider in this work both the Cartesian and the strong product of graphs. Exact values in terms of invariants of the factors are presented for the first mentioned product. For the strong product, it is shown that such a result does not exist, but an exact result for trees is proved.

In this note, we provide bijective proofs of some identities involving the Bell number, as previously requested. Our arguments may be extended to yield a generalization in terms of complete Bell polynomials. We also provide a further interpretation for a related difference of Catalan numbers in terms of the inclusion-exclusion principle.

Given a graph $G=(V,E)$ and $A_1,A_2,\dots ,A_r$, mutually disjoint nonempty subsets of $V$ where $|A_i|\le |V|/r$ for each $i$, we say that $G$ is spanning equi-cyclable with respect to $A_1,A_2,\dots ,A_r$ if there exist mutually disjoint cycles $C_1,C_2,\dots ,C_r$ that span $G$ such that $C_i$ contains $A_i$ for every $i$ and $C_i$ contains either $\lfloor |V|/r\rfloor$ vertices or $\lceil |V|/r\rceil$ vertices. Moreover, $G$ is $r$-$spanning-equicyclable$ if $G$ is spanning equi-cyclable with respect to $A_1,A_2,\dots ,A_r$ for every such mutually disjoint nonempty subsets of $V$. We define the spanning equi-cyclability of $G$ to be $r$ if $G$ is $k$-spanning-equicyclable for $k=1,2,\dots ,r$ but is not $(r+1)$-spanning-equicyclable. Another approach on the restriction of the $A_i$’s is the following. We say that $G=(V,E)$ is $r$-$cyclableoforder$ $t$ if it is cyclable with respect to $A_1,A_2,\dots ,A_r$ for any $r$ nonempty mutually disjoint subsets $A_1,A_2,\dots ,A_r$ of $V$ such that $|A_1\cup A_2\cup \dots \cup A_r|\le t$. The $r$-cyclability of $G$ is $t$ if $G$ is $r$-cyclable of order $k$ for $k=r,r+1,\dots ,t$ but is not $r$-cyclable of order $t+1$. On the other hand, the cyclability of $G$ of order $t$ is $r$ if $G$ is $k$-cyclable of order $t$ for $k=1,2,\dots ,r$ but is not $(r+1)$-cyclable of order $t$. In this paper, we study sufficient conditions for spanning equi-cyclability and $r$-cyclability of order $t$ as well as other related problems.

The existence of additive BIB designs and 2 pairwise additive BIB designs has been discussed with direct and recursive constructions in [6, 9]. In this paper, by reorganizing some methods of constructing pairwise additive BIB designs from other combinatorial structures, it is shown that 3 pairwise additive $B(v,2,1)$ can be constructed for any integer $v\ge 6$.

A lot of research has been spent determining the domination numbers, ${\gamma }_{m,n}$, of grid graphs. But relatively little effort has been given to constructing minimum dominating sets of grid graphs. In this paper, we introduce a method for constructing $\gamma$-sets of grid graphs $G_{m,n}$ for all $m\ge 16$ and $n\ge 16$. Further, for $G_{m,n}$, $m<16$, $m\ne 12,13$, we show how particular $\gamma$-sets can be used to construct $\gamma$-sets for other grid graphs.