A new forbidden pair for 6-contractible edges

An edge of a $k$-connected graph is said to be $k$-contractible if the contraction of the edge results in a $k$-connected graph. If every $k$-connected graph with no $k$-contractible edge has either $H_1$ or $H_2$ as a subgraph, then an unordered pair of graphs $\{H_1,H_2\}$ is said to be a forbidden pair for $k$-contractible edges. We prove that $\{K_1+3K_2,K_1+(P_3\cup K_2)\}$ is a forbidden pair for 6-contractible edges, which is an extension of a previous result due to Ando and Kawarabayashi.     

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

Proof of a conjecture on monomial graphs

Let e be a positive integer, p be an odd prime, $q=p^e$, and ${\mathbb{F}}_q$ be the finite field of q elements. Let $f,g\in {\mathbb{F}}_q[X,Y]$. The graph $G_q(f,g)$ is a bipartite graph with vertex partitions $P={\mathbb{F}}_q^3$ and $L={\mathbb{F}}_q^3$, and edges defined as follows: a vertex $(p)=(p_1,p_2,p_3)\in P$ is adjacent to a vertex $[l]=[l_1,l_2,l_3]\in L$ if and only if $p_2+l_2=f(p_1,l_1)$ and $p_3+l_3=g(p_1,l_1)$. If $f=XY$ and $g=X{Y}^2$, the graph $G_q(XY,X{Y}^2)$ contains no cycles of length less than eight and is edge-transitive. Motivated by certain questions in extremal graph theory and finite geometry, people search for examples of graphs $G_q(f,g)$ containing no cycles of length less than eight and not isomorphic to the graph $G_q(XY,X{Y}^2)$, even without requiring them to be edge-transitive. So far, no such graphs $G_q(f,g)$ have been found. It was conjectured that if both f and g are monomials, then no such graphs exist. In this paper we prove the conjecture.     

A sufficient condition for DP-4-colorability

DP-coloring of a simple graph is a generalization of list coloring, and also a generalization of signed coloring of signed graphs. It is known that for each $k\in \{3,4,5,6\}$, every planar graph without $C_k$ is 4-choosable. Furthermore, Jin et al. (2016) showed that for each $k\in \{3,4,5,6\}$, every signed planar graph without $C_k$ is signed 4-choosable. In this paper, we show that for each $k\in \{3,4,5,6\}$, every planar graph without $C_k$ is 4-DP-colorable, which is an extension of the above results.     

Resolvable 4-cycle group divisible designs with two associate classes: Part size even

Let ${\lambda }_1{K}_a$ denote the graph on a vertices with ${\lambda }_1$ edges between every pair of vertices. Take p copies of this graph ${\lambda }_1{K}_a$, and join each pair of vertices in different copies with ${\lambda }_2$ edges. The resulting graph is denoted by $K(a,p;{\lambda }_1,{\lambda }_2)$, a graph that was of particular interest to Bose and Shimamoto in their study of group divisible designs with two associate classes. The existence of z-cycle decompositions of this graph have been found when $z\in \{3,4\}$. In this paper we consider resolvable decompositions, finding necessary and sufficient conditions for a 4-cycle factorization of $K(a,p;{\lambda }_1,{\lambda }_2)$ (when ${\lambda }_1$ is even) or of $K(a,p;{\lambda }_1,{\lambda }_2)$ minus a 1-factor (when ${\lambda }_1$ is odd) whenever a is even.     

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.     

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

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.     

The minimum volume of subspace trades

A subspace bitrade of type $T_q(t,k,v)$ is a pair $(T_0,T_1)$ of two disjoint nonempty collections of $k$-dimensional subspaces of a $v$-dimensional space $V$ over the finite field of order $q$ such that every $t$-dimensional subspace of $V$ is covered by the same number of subspaces from $T_0$ and $T_1$. In a previous paper, the minimum cardinality of a subspace $T_q(t,t+1,v)$ bitrade was established. We generalize that result by showing that for admissible $v$, $t$, and $k$, the minimum cardinality of a subspace $T_q(t,k,v)$ bitrade does not depend on $k$. An example of a minimum bitrade is represented using generator matrices in the reduced echelon form. For $t=1$, the uniqueness of a minimum bitrade is proved.     

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.     

On the distance between linear codes

Let V be an n-dimensional vector space over the finite field consisting of q elements and let ${\mathrm{\Gamma }}_k(V)$ be the Grassmann graph formed by k-dimensional subspaces of V, $1<k<n-1$. Denote by $\mathrm{\Gamma }{(n,k)}_q$ the restriction of ${\mathrm{\Gamma }}_k(V)$ to the set of all non-degenerate linear ${[n,k]}_q$ codes. We show that for any two codes the distance in $\mathrm{\Gamma }{(n,k)}_q$ coincides with the distance in ${\mathrm{\Gamma }}_k(V)$ only in the case when $n<{(q+1)}^2+k-2$, i.e. if n is sufficiently large then for some pairs of codes the distances in the graphs ${\mathrm{\Gamma }}_k(V)$ and $\mathrm{\Gamma }{(n,k)}_q$ are distinct. We describe one class of such pairs.     

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