A stability version for a theorem of Erdős on nonhamiltonian graphs

Let $n,d$ be integers with $1\le d\le ?\frac{n?1}{2}?$, and set $h(n,d)?\left(\genfrac{}{}{0ex}{}{n?d}{2}\right)+d^2$ and $e(n,d)?max\{h(n,d),h(n,?\frac{n?1}{2}?)\}$. Because $h(n,d)$ is quadratic in $d$, there exists a $d_0\left(n\right)=(n∕6)+O\left(1\right)$ such that

$e(n,1)>e(n,2)>?>e(n,d_0)=e(n,d_0+1)=?=e\left(n,?\frac{n?1}{2}?\right).$

A theorem by Erd?s states that for $d\le ?\frac{n?1}{2}?$, any $n$-vertex nonhamiltonian graph $G$ with minimum degree $\delta \left(G\right)\ge d$ has at most $e(n,d)$ edges, and for $d>d_0\left(n\right)$ the unique sharpness example is simply the graph $K_n?E\left(K_{?(n+1)∕2?}\right)$. Erd?s also presented a sharpness example $H_{n,d}$ for each $1\le d\le d_0\left(n\right)$.We show that if $d<d_0\left(n\right)$ and a $2$-connected, nonhamiltonian $n$-vertex graph $G$ with $\delta \left(G\right)\ge d$ has more than $e(n,d+1)$ edges, then $G$ is a subgraph of $H_{n,d}$. Note that $e(n,d)?e(n,d+1)=n?3d?2\ge n∕2$ whenever $d<d_0\left(n\right)?1$.     

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.     

Automorphism groups of Cayley graphs generated by block transpositions and regular Cayley maps

This paper deals with the Cayley graph $\mathrm{Cay}({\mathrm{Sym}}_n,T_n)$, where the generating set consists of all block transpositions. A motivation for the study of these particular Cayley graphs comes from current research in Bioinformatics. As the main result, we prove that $\text{Aut}\left(\mathrm{Cay}({\mathrm{Sym}}_n,T_n)\right)$ is the product of the left translation group and a dihedral group ${\mathsf{D}}_{n+1}$ of order $2(n+1)$. The proof uses several properties of the subgraph $\Gamma$ of $\mathrm{Cay}({\mathrm{Sym}}_n,T_n)$ induced by the set $T_n$. In particular, $\Gamma$ is a $2(n?2)$-regular graph whose automorphism group is ${\mathsf{D}}_{n+1},$ $\Gamma$ has as many as $n+1$ maximal cliques of size $2$, and its subgraph $\Gamma \left(V\right)$ whose vertices are those in these cliques is a 3-regular, Hamiltonian, and vertex-transitive graph. A relation of the unique cyclic subgroup of ${\mathsf{D}}_{n+1}$ of order $n+1$ with regular Cayley maps on ${\text{Sym}}_n$ is also discussed. It is shown that the product of the left translation group and the latter group can be obtained as the automorphism group of a non-$t$-balanced regular Cayley map on ${\text{Sym}}_n$.     

Tensors,matchings and codes

We exploit the structure of the critical orbital sets of symmetry classes of tensors associated to sign uniform partitions and we establish new connections between symmetry classes of tensors, matchings on bipartite graphs and coding theory. In particular, we prove that the orthogonal dimension of the critical orbital sets associated to single hook partitions $\lambda =(w\text{,}{1}^{n-w})$ equals the value of the coding theoretic function $A(n\text{,}4\text{,}w)$. When $w=2$ we reobtain this number as the independence number of the Dynkin diagram $A_{n-1}$.     

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.     

Minimal homogeneous Steiner 2-(v,3) trades

A Steiner 2-$(v,3)$ trade is a pair $(T_1,T_2)$ of disjoint partial Steiner triple systems, each on the same set of $v$ points, such that each pair of points occurs in $T_1$ if and only if it occurs in $T_2$. A Steiner 2-$(v,3)$ trade is called d-homogeneous if each point occurs in exactly d blocks of $T_1$ (or $T_2$). In this paper we construct minimal d-homogeneous Steiner 2-$(v,3)$ trades of foundation $v$ and volume $\mathit{dv}/3$ for sufficiently large values of $v$. (Specifically, $v>3(1.75d^2+3)$ if $v$ is divisible by 3 and $v>d(4^{d/3+1}+1)$ otherwise.)     

Basins of attraction of equilibrium points of second order difference equations

We investigate the basins of attraction of equilibrium points and period-two solutions of the difference equation of the form $x_{n+1}=f(x_n,x_{n?1})\text{,}n=0,1,\dots \text{,}$ where $f$ is decreasing in the first and increasing in the second variable. We show that the boundaries of the basins of attraction of different locally asymptotically stable equilibrium points are in fact the global stable manifolds of neighboring saddle or non-hyperbolic equilibrium points.