Degree Ramsey numbers for even cycles

Let $H\stackrel{s}{?}G$ denote that any $s$-coloring of $E\left(H\right)$ contains a monochromatic $G$. The degree Ramsey number of a graph $G$, denoted by $R_{\Delta }(G,s)$, is $min\{\Delta \left(H\right):H\stackrel{s}{?}G\}$. We consider degree Ramsey numbers where $G$ is a fixed even cycle. Kinnersley, Milans, and West showed that $R_{\Delta }(C_{2k},s)\ge 2s$, and Kang and Perarnau showed that $R_{\Delta }(C_4,s)=\Theta \left(s^2\right)$. Our main result is that $R_{\Delta }(C_6,s)=\Theta \left(s^{3∕2}\right)$ and $R_{\Delta }(C_{10},s)=\Theta \left(s^{5∕4}\right)$. Additionally, we substantially improve the lower bound for $R_{\Delta }(C_{2k},s)$ for general $k$.     

The multipartite Ramsey number for the 3-path of length three

We study the Ramsey number for the 3-uniform loose path of length three, $P_3^3$, and $n$ colors. We show that $R(P_3^3;n)\le {\lambda }_{0}n+7\sqrt{n}$, for some explicit constant ${\lambda }_0=1.97466\dots$.     

Turán numbers of vertex-disjoint cliques in r-partite graphs

For two graphs $G$ and $H$, the Turán number$ex(G,H)$ is the maximum number of edges in a subgraph of $G$ that contains no copy of $H$. Chen, Li, and Tu determined the Turán numbers $ex(K_{m,n},k{K}_2)$ for all $k\ge 1$ Chen et al. (2009). In this paper we will determine the Turán numbers $ex(K_{a_1,\dots ,a_r},k{K}_r)$ for all $r\ge 3$ and $k\ge 1$.     

Some multicolor bipartite Ramsey numbers involving cycles and a small number of colors

For bipartite graphs $G_1,G_2,\dots ,G_k$, the bipartite Ramsey number $b(G_1,G_2,\dots ,G_k)$ is the least positive integer $b$ so that any coloring of the edges of $K_{b,b}$ with $k$ colors will result in a copy of $G_i$ in the $i$th color for some $i$. In this paper, our main focus will be to bound the following numbers: $b(C_{2t_1},C_{2t_2})$ and $b(C_{2t_1},C_{2t_2},C_{2t_3})$ for all $t_i\ge 3,$$b(C_{2t_1},C_{2t_2},C_{2t_3},C_{2t_4})$ for $3\le t_i\le 9,$ and $b(C_{2t_1},C_{2t_2},C_{2t_3},C_{2t_4},C_{2t_5})$ for $3\le t_i\le 5.$ Furthermore, we will also show that these mentioned bounds are generally better than the bounds obtained by using the best known Zarankiewicz-type result.     

Sums of powers of Catalan triangle numbers

In this paper, we consider combinatorial numbers ${\left(C_{m,k}\right)}_{m\ge 1,k\ge 0}$, mentioned as Catalan triangle numbers where $C_{m,k}?\left(\genfrac{}{}{0ex}{}{m?1}{k}\right)?\left(\genfrac{}{}{0ex}{}{m?1}{k?1}\right)$. These numbers unify the entries of the Catalan triangles $B_{n,k}$ and $A_{n,k}$ for appropriate values of parameters $m$ and $k$, i.e., $B_{n,k}=C_{2n,n?k}$ and $A_{n,k}=C_{2n+1,n+1?k}$. In fact, these numbers are suitable rearrangements of the known ballot numbers and some of these numbers are the well-known Catalan numbers $C_n$ that is $C_{2n,n?1}=C_{2n+1,n}=C_n$.We present identities for sums (and alternating sums) of $C_{m,k}$, squares and cubes of $C_{m,k}$ and, consequently, for $B_{n,k}$ and $A_{n,k}$. In particular, one of these identities solves an open problem posed in Gutiérrez et al. (2008). We also give some identities between ${\left(C_{m,k}\right)}_{m\ge 1,k\ge 0}$ and harmonic numbers ${\left(H_n\right)}_{n\ge 1}$. Finally, in the last section, new open problems and identities involving ${\left(C_n\right)}_{n\ge 0}$ are conjectured.     

Proper connection and size of graphs

An edge-coloured graph $G$ is called properly connected if any two vertices are connected by a path whose edges are properly coloured. The proper connection number of a connected graph $G,$ denoted by $\mathrm{pc}\left(G\right)$, is the smallest number of colours that are needed in order to make $G$ properly connected. Our main result is the following: Let $G$ be a connected graph of order $n$ and $k\ge 2$. If $\left|E\left(G\right)\right|\ge \left(\genfrac{}{}{0ex}{}{n?k?1}{2}\right)+k+2$, then $\mathrm{pc}\left(G\right)\le k$ except when $k=2$ and $G\in \{G_1,G_2\},$ where $G_1=K_1\vee (2K_1+K_2)$ and $G_2=K_1\vee (K_1+2K_2).$     

The smallest surface that contains all signed graphs on K4,n

Finding the smallest number of crosscaps that suffice to orientation-embed every edge signature of the complete bipartite graph $K_{m,n}$ is an open problem. In this paper that number for the complete bipartite graph $K_{4,n}$, $n\ge 4$, is determined by using diamond products of signed graphs. The number is $2?\frac{n?1}{2}?+1$, which is attained by $K_{4,n}$ with exactly 1 negative edge, except that when $n=4$, the number is 4, which is attained by $K_{4,4}$ with exactly 4 independent negative edges.     

Hankel determinants of linear combinations of consecutive Catalan-like numbers

Let ${\left(a_n\right)}_{n\ge 0}$ be a sequence of the Catalan-like numbers. We evaluate Hankel determinants $det{[\lambda a_{i+j}+\mu a_{i+j+1}]}_{0\le i,j\le n}$ and $det{[\lambda a_{i+j+1}+\mu a_{i+j+2}]}_{0\le i,j\le n}$ for arbitrary coefficients $\lambda$ and $\mu$. Our results unify many known results of Hankel determinant evaluations for classic combinatorial counting coefficients, including the Catalan, Motzkin and Schröder numbers.     

A note on conservative galaxies,Skolem systems,cyclic cycle decompositions,and Heffter arrays

The conservative number of a graph $G$ is the minimum positive integer $M$, such that $G$ admits an orientation and a labeling of its edges by distinct integers in $\{1,2,\dots ,M\}$, such that at each vertex of degree at least three, the sum of the labels on the in-coming edges is equal to the sum of the labels on the out-going edges. A graph is conservative if $M=\left|E\left(G\right)\right|$. It is worth noting that determining whether certain biregular graphs are conservative is equivalent to find integer Heffter arrays.In this work we show that the conservative number of a galaxy (a disjoint union of stars) of size $M$ is $M$ for $M\equiv 0$, $3(mod4)$, and $M+1$ otherwise. Consequently, given positive integers $m_1$, $m_2$, …, $m_n$ with $m_i\ge 3$ for $1\le i\le n$, we construct a cyclic $(m_1,m_2,\dots ,m_n)$-cycle system of infinitely many circulant graphs, generalizing a result of Bryant, Gavlas and Ling (2003). In particular, it allows us to construct a cyclic $(m_1,m_2,\dots ,m_n)$-cycle system of the complete graph $K_{2M+1}$, where $M={\sum }_{i=1}^n{m}_i$. Also, we prove necessary and sufficient conditions for the existence of a cyclic $(m_1,m_2,\dots ,m_n)$-cycle system of $K_{2M+2}?F$, where $F$ is a 1-factor. Furthermore, we give a sufficient condition for a subset of ${\mathbb{Z}}_v?\left\{0\right\}$ to be sequenceable.     

Ramsey number of multiple copies of stars

Let G and H be simple graphs. The Ramsey number $r(G,H)$ is the minimum integer N such that any red-blue-coloring of edges of $K_N$ contains either a red copy of G or a blue copy of H. Let $m{K}_{1,t}$ denote m vertex-disjoint copies of $K_{1,t}$. A lower bound is that $r(m{K}_{1,t},n{K}_{1,s})\ge m(t+1)+n?1$. Burr, Erd?s and Spencer proved that this bound is indeed the Ramsey number $r(m{K}_{1,t},n{K}_{1,s})$ for $t=s=3$, $m\ge 2$ and $m\ge n$. In this paper, we show that this bound is the Ramsey number $r(m{K}_{1,t},n{K}_{1,s})$ for $t\ge s=3,m\ge 2$ and $m\ge n$. We also show that this bound is the Ramsey number $r(m{K}_{1,t},n{K}_{1,s})$ for $s\ge 4,t>\frac{s(s?1)}{2}$ and $m>n$.     

Ramsey numbers of odd cycles versus larger even wheels

The generalized Ramsey number $R(G_1,G_2)$ is the smallest positive integer $N$ such that any red–blue coloring of the edges of the complete graph $K_N$ either contains a red copy of $G_1$ or a blue copy of $G_2$. Let $C_m$ denote a cycle of length $m$ and $W_n$ denote a wheel with $n+1$ vertices. In 2014, Zhang, Zhang and Chen determined many of the Ramsey numbers $R(C_{2k+1},W_n)$ of odd cycles versus larger wheels, leaving open the particular case where $n=2j$ is even and $k<j<3k∕2$. They conjectured that for these values of $j$ and $k$, $R(C_{2k+1},W_{2j})=4j+1$. In 2015, Sanhueza-Matamala confirmed this conjecture asymptotically, showing that $R(C_{2k+1},W_{2j})\le 4j+334$. In this paper, we prove the conjecture of Zhang, Zhang and Chen for almost all of the remaining cases. In particular, we prove that $R(C_{2k+1},W_{2j})=4j+1$ if $j?k\ge 251$, $k<j<3k∕2$, and $j\ge 212299$.