The NLC-width and clique-width for powers of graphs of bounded tree-width

The $k$-power graph of a graph $G$ is a graph with the same vertex set as $G$, in that two vertices are adjacent if and only if, there is a path between them in $G$ of length at most $k$. A $k$-tree-power graph is the $k$-power graph of a tree, a $k$-leaf-power graph is the subgraph of some $k$-tree-power graph induced by the leaves of the tree.We show that (1) every $k$-tree-power graph has NLC-width at most $k+2$ and clique-width at most $k+2+max\{?\frac{k}{2}??1,0\}$, (2) every $k$-leaf-power graph has NLC-width at most $k$ and clique-width at most $k+max\{?\frac{k}{2}??2,0\}$, and (3) every $k$-power graph of a graph of tree-width $l$ has NLC-width at most ${(k+1)}^{l+1}?1$, and clique-width at most $2?{(k+1)}^{l+1}?2$.     

Counting humps and peaks in generalized Motzkin paths

Let us call a lattice path in $\mathbb{Z}\times \mathbb{Z}$ from $(0,0)$ to $(n,0)$ using $U=(1,k)$, $D=(1,?1)$, and $H=(a,0)$ steps and never going below the $x$-axis, a $(k,a)$-path (of order $n$). A super   $(k,a)$-path is a $(k,a)$-path which is permitted to go below the $x$-axis. We relate the total number of humps in all of the $(k,a)$-paths of order $n$ to the number of super $(k,a)$-paths, where a hump is defined to be a sequence of steps of the form $U{H}^{i}D$, $i\ge 0$. This generalizes recent results concerning the cases when $k=1$ and $a=1$ or $a=\infty$. A similar relation may be given involving peaks (consecutive steps of the form $UD$).     

On mixed Moore graphs

The Moore bound for a directed graph of maximum out-degree d and diameter k is $M_{d,k}=1+d+d^2+\cdots +d^k$. It is known that digraphs of order $M_{d,k}$ (Moore digraphs) do not exist for $d>1$ and $k>1$. Similarly, the Moore bound for an undirected graph of maximum degree d and diameter k is $M_{d,k}^{*}=1+d+d(d-1)+\cdots +d(d-1{)}^{k-1}$. Undirected Moore graphs only exist in a small number of cases. Mixed (or partially directed) Moore graphs generalize both undirected and directed Moore graphs. In this paper, we shall show that all known mixed Moore graphs of diameter $k=2$ are unique and that mixed Moore graphs of diameter $k⩾3$ do not exist.     

Equation-regular sets and the Fox–Kleitman conjecture

Given $k\ge 1$, the Fox–Kleitman conjecture from 2006 states that there exists a nonzero integer $b$ such that the $2k$-variable linear Diophantine equation

$\sum _{i=1}^k(x_i?y_i)=b$

is $(2k?1)$-regular. This is best possible, since Fox and Kleitman showed that for all $b\ge 1$, this equation is not $2k$-regular. While the conjecture has recently been settled for all $k\ge 2$, here we focus on the case $k=3$ and determine the degree of regularity of the corresponding equation for all $b\ge 1$. In particular, this independently confirms the conjecture for $k=3$. We also briefly discuss the case $k=4$.     

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).$     

A new approach to the chromatic number of the square of Kneser graph K(2k+1,k)

The vertices of Kneser graph $K(n,k)$ are the subsets of $\{1,2,\dots ,n\}$ of cardinality $k$, two vertices are adjacent if and only if they are disjoint. The square $G^2$ of a graph $G$ is defined on the vertex set of $G$ with two vertices adjacent if their distance in $G$ is at most 2. Z. Füredi, in 2002, proposed the problem of determining the chromatic number of the square of the Kneser graph. The first non-trivial problem arises when $n=2k+1$. It is believed that $\chi \left(K^2(2k+1,k)\right)=2k+c$ where $c$ is a constant, and yet the problem remains open. The best known upper bounds are by Kim and Park: $8k∕3+20∕3$ for 1$k\ge 3$ (Kim and Park, 2014) and $32k∕15+32$ for $k\ge 7$ (Kim and Park, 2016). In this paper, we develop a new approach to this coloring problem by employing graph homomorphisms, cartesian products of graphs, and linear congruences integrated with combinatorial arguments. These lead to $\chi \left(K^2(2k+1,k)\right)\le 5k∕2+c$, where $c$ is a constant in $\{5∕2,9∕2,5,6\}$, depending on $k\ge 2$.     

Non-level semi-standard graded Cohen–Macaulay domain with h-vector (h0,h1,h2)

Let $\mathbb{k}$ be an algebraically closed field of characteristic 0, and $A={?}_{i\in \mathbb{N}}{A}_i$ a Cohen–Macaulay graded domain with $A_0=\mathbb{k}$. If A is semi-standard graded (i.e., A is finitely generated as a $\mathbb{k}[A_1]$-module), it has the h-vector$(h_0,h_1,\dots ,h_s)$, which encodes the Hilbert function of A. From now on, assume that $s=2$. It is known that if A is standard graded (i.e., $A=\mathbb{k}[A_1]$), then A is level. We will show that, in the semi-standard case, if A is not level, then $h_1+1$ divides $h_2$. Conversely, for any positive integers h and n, there is a non-level A with the h-vector $(1,h,(h+1)n)$. Moreover, such examples can be constructed as Ehrhart rings (equivalently, normal toric rings).     

Singular discrete and continuous mixed boundary value problems

For each $n\in \mathbb{N}$, $n\ge 2$, we prove the existence of a solution $(u_0,\dots ,u_n)\in {\mathbb{R}}^{n+1}$ of the singular discrete problem $\frac{1}{h^2}{\Delta }^2{u}_{k?1}+f(t_k,u_k)=0\text{,}k=1,\dots ,n?1\text{,}$$\Delta u_0=0\text{,}{u}_n=0\text{,}$ where $u_k>0$ for $k=0,\dots ,n?1$. Here $T\in (0,\infty )$, $h=\frac{T}{n}$, $t_k=hk$, $f(t,x):[0,T]\times (0,\infty )\to \mathbb{R}$ is continuous and has a singularity at $x=0$. We prove that for $n\to \infty$ the sequence of solutions of the above discrete problems converges to a solution $y$ of the corresponding continuous boundary value problem $y^{″}\left(t\right)+f(t,y\left(t\right))=0\text{,}$$y^{\prime }\left(0\right)=0\text{,}y\left(T\right)=0\text{.}$     

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$.     

Enumeration formulas for standard Young tableaux of nearly hollow rectangular shapes

This paper considers the enumeration problem of a generalization of standard Young tableau (SYT) of truncated shape. Let $\lambda ?\mu |\left\{(i_0,j_0)\right\}$ be the SYT of shape $\lambda$ truncated by $\mu$ whose upper left cell is $(i_0,j_0)$, where $\lambda$ and $\mu$ are partitions of integers. The summation representation of the number of SYT of the truncated shape $(n+k+2,{(n+2)}^{m+1})?\left(n^m\right)|\left\{(2,2)\right\}$ is derived. Consequently, three closed formulas for SYT of hollow shapes are obtained, including the cases of (i). $m=n=1$, (ii). $k=0$, and (iii). $k=1,m=n$. Finally, an open problem is posed.     

Partitions of natural numbers with the same weighted representation functions

TextFor any given two positive integers $k_1$ and $k_2$, and any set A of nonnegative integers, let $r_{k_1,k_2}(A,n)$ denote the number of solutions of the equation $n=k_1{a}_1+k_2{a}_2$ with $a_1,a_2\in A$. In this paper, we determine all pairs $k_1,k_2$ of positive integers for which there exists a set $A?\mathbb{N}$ such that $r_{k_1,k_2}(A,n)=r_{k_1,k_2}(\mathbb{N}?A,n)$ for all $n?n_0$. We also pose several problems for further research.VideoFor a video summary of this paper, please click here or visit http://www.youtube.com/watch?v=EnezEsJl0OY.     

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.