A note on the smallest connected non-traceable cubic bipartite planar graph

A graph is traceable if it contains a Hamiltonian path. We present a connected non-traceable cubic bipartite planar graph with 52 vertices and prove that there are no smaller such graphs.     

Decompositions of graphs via generalized graceful labelings

In [Pasotti, A., On d-graceful labelings, to appear on Ars Combin] a d-divisible α-labeling is defined as a generalization of the classical one of Rosa (see [Rosa, A., On certain valuations of the vertices of a graph, Theory of Graphs (Internat. Symposium, Rome, July 1966), Gordon and Breach, N. Y. and Dunod Paris (1967), 349–355]) and, similarly to the classical case, it is proved that there exists a link between d-divisible α-labelings of a graph Γ and cyclic Γ-decompositions. In [Benini, A., and Pasotti, A., Decompositions of complete multipartite graphs via generalized graceful labelings, submitted. (arXiv:1210.4370)] we have dealt with the existence of d-divisible α-labelings of caterpillars and certain classes of cycles and hairy cycles and the resulting possible decompositions.     

Planar bipartite biregular degree sequences

A pair of sequences of natural numbers is called planar if there exists a simple, bipartite, planar graph for which the given sequences are the degree sequences of its parts. For a pair to be planar, the sums of the sequences have to be equal and Euler’s inequality must be satisfied. Pairs that verify these two necessary conditions are called admissible. We prove that a pair of constant sequences is planar if and only if it is admissible (such pairs can be easily listed) and is different from $\left(3^5\right|3^5)$ and $\left(3^{25}\right|5^{15})$.     

From graceful labellings of paths to cyclic solutions of the Oberwolfach problem

Constraints are given on graceful labellings for paths that allow them to be used to construct cyclic solutions to the Oberwolfach Problem. We give examples of graceful labellings meeting these constraints and hence, infinitely many new families of cyclic solutions can be constructed.     

A C5-decomposition of the λ-fold line graph of the complete graph

In 1996, Cox and Rodger [Cycle systems of the line graph of the complete graph, J. Graph Theory 21 (1996) 173–182] raised the following question: For what values of $m$ and $n$ does there exist an $m$-cycle decomposition of $L\left(K_n\right)?$ In this paper, the above question is answered for $m=5.$ In fact, it is shown that $L\left(K_n\right)\left(\lambda \right),$ the $\lambda$-fold line graph of the complete graph $K_n,$ has a $C_5$-decomposition if and only if $5\mid \lambda \left(\genfrac{}{}{0ex}{}{n}{2}\right)(n?2)$ and $n\ge 4.$     

Caterpillars with maximum degree 3 are antimagic

Let $G=(V,E)$ be a connected graph with $m$ edges. An antimagic labeling of $G$ is a one-to-one mapping from $E$ to $\{1,2,\dots ,m\}$ such that the vertex sum (i.e., sum of the labels assigned to edges incident to a vertex) for distinct vertices are different. A graph $G$ is called antimagic if $G$ has an antimagic labeling. It was conjectured by Hartsfield and Ringel that every tree other than $K_2$ is antimagic. The conjecture remains open though it was verified for trees with some constrains. Caterpillars are an important subclass of trees. This paper shows caterpillars with maximum degree 3 are antimagic, which gives an affirmative answer to an open problem of Lozano et al. (2019).     

Perfect matchings extend to two or more hamiltonian cycles in hypercubes

Kreweras conjectured that every perfect matching of a hypercube $Q_n$ for $n\ge 2$ can be extended to a hamiltonian cycle of $Q_n$. Fink confirmed the conjecture to be true. It is more general to ask whether every perfect matching of $Q_n$ for $n\ge 2$ can be extended to two or more hamiltonian cycles of $Q_n$. In this paper, we prove that every perfect matching of $Q_n$ for $n\ge 4$ can be extended to at least $2^{2^{n?4}}$ different hamiltonian cycles of $Q_n$.     

Complete graphs and complete bipartite graphs without rainbow path

Motivated by Ramsey-type questions, we consider edge-colorings of complete graphs and complete bipartite graphs without rainbow path. Given two graphs $G$ and $H$, the $k$-colored Gallai–Ramsey number $g{r}_k(G:H)$ is defined to be the minimum integer $n$ such that $\left(\genfrac{}{}{0ex}{}{n}{2}\right)\ge k$ and for every $N\ge n$, every rainbow $G$-free coloring (using all $k$ colors) of the complete graph $K_N$ contains a monochromatic copy of $H$. In this paper, we first provide some exact values and bounds of $g{r}_k(P_5:K_t)$. Moreover, we define the $k$-colored bipartite Gallai–Ramsey number $bg{r}_k(G:H)$ as the minimum integer $n$ such that $n^2\ge k$ and for every $N\ge n$, every rainbow $G$-free coloring (using all $k$ colors) of the complete bipartite graph $K_{N,N}$ contains a monochromatic copy of $H$. Furthermore, we describe the structures of complete bipartite graph $K_{n,n}$ with no rainbow $P_4$ and $P_5$, respectively. Finally, we find the exact values of $bg{r}_k(P_4:K_{s,t})$ ($1\le s\le t$), $bg{r}_k(P_4:F)$ (where $F$ is a subgraph of $K_{s,t}$), $bg{r}_k(P_5:K_{1,t})$ and $bg{r}_k(P_5:K_{2,t})$ by using the structural results.     

Antimagic orientations of disconnected even regular graphs

A $labeling$ of a digraph $D$ with $m$ arcs is a bijection from the set of arcs of $D$ to $\{1,2,\dots ,m\}$. A labeling of $D$ is $antimagic$ if no two vertices in $D$ have the same vertex-sum, where the vertex-sum of a vertex $u\in V\left(D\right)$ for a labeling is the sum of labels of all arcs entering $u$ minus the sum of labels of all arcs leaving $u$. An orientation $D$ of a graph $G$ is $antimagic$ if $D$ has an antimagic labeling. Hefetz et al. (2010) raised the question: Does every graph admit an antimagic orientation? It had been proved that every 2$d$-regular graph with at most two odd components has an antimagic orientation. In this paper, we consider 2$d$-regular graphs with more than two odd components. We show that every 2$d$-regular graph with $k(3\le k\le 5d+4)$ odd components has an antimagic orientation. And we show that each 2$d$-regular graph with $k(k\ge 5d+5)$ odd components admits an antimagic orientation if each odd component has at least $2x_0+5$ vertices with $x_0=?\frac{k?(5d+4)}{2d?2}?$.     

Unipancyclic matroids

Analogous to the concept of uniquely pancyclic graphs, we define a uniquely pancyclic (UPC) matroid of rank $r$ to be a (simple) rank-$r$ matroid containing exactly one circuit of each length $?$ for $3\le ?\le r+1$. Our discussion addresses the existence of graphic, binary, and transversal representations of UPC matroids. Using Shi’s results, which catalogued exactly seven non-isomorphic UPC graphs, we produce a nongraphic binary UPC matroid of rank 24. We consider properties of binary UPC matroids in general, and prove that all binary UPC matroids have a connectivity of $2$.     

Antimagic orientation of Halin graphs

An antimagic labeling of a digraph $D$ with $n$ vertices and $m$ arcs is a bijection from the set of arcs of $D$ to $\{1,2,\dots ,m\}$ such that all $n$ oriented vertex sums are pairwise distinct, where an oriented vertex sum of a vertex is the sum of labels of all arcs entering that vertex minus the sum of labels of all arcs leaving it. Hefetz, Mütze and Schwartz conjectured every connected undirected graph admits an antimagic orientation. In this paper, we support this conjecture by proving that every Halin graph admits an antimagic orientation.     

Enclosings of decompositions of complete multigraphs in 2-edge-connected r-factorizations

A decomposition of a multigraph $G$ is a partition of its edges into subgraphs $G\left(1\right),\dots ,G\left(k\right)$. It is called an $r$-factorization if every $G\left(i\right)$ is $r$-regular and spanning. If $G$ is a subgraph of $H$, a decomposition of $G$ is said to be enclosed in a decomposition of $H$ if, for every $1\le i\le k$, $G\left(i\right)$ is a subgraph of $H\left(i\right)$.Feghali and Johnson gave necessary and sufficient conditions for a given decomposition of $\lambda K_n$ to be enclosed in some 2-edge-connected $r$-factorization of $\mu K_m$ for some range of values for the parameters $n$, $m$, $\lambda$, $\mu$, $r$: $r=2$, $\mu >\lambda$ and either $m\ge 2n?1$, or $m=2n?2$ and $\mu =2$ and $\lambda =1$, or $n=3$ and $m=4$. We generalize their result to every $r\ge 2$ and $m\ge 2n?2$. We also give some sufficient conditions for enclosing a given decomposition of $\lambda K_n$ in some 2-edge-connected $r$-factorization of $\mu K_m$ for every $r\ge 3$ and $m>(2?C)n$, where $C$ is a constant that depends only on $r$, $\lambda$ and $\mu$.     

Gallai’s path decomposition conjecture for graphs of small maximum degree

Gallai’s path decomposition conjecture states that the edges of any connected graph on $n$ vertices can be decomposed into at most $\frac{n+1}{2}$ paths. We confirm that conjecture for all graphs with maximum degree at most five.     

On the smallest non-trivial tight sets in Hermitian polar spaces H(d,q2), d even

We show that every $x$-tight set of a Hermitian polar spaces $\mathrm{H}(2n,q^2)$, $n\ge 2$, is the union of $x$ disjoint generators of the polar space provided that $x\le \frac{1}{2}(q+1)$. This was known before only when $n\in \{2,3\}$. This result is a contribution to the conjecture that the smallest $x$-tight set of $H(2n,q^2)$ that is not a union of disjoint generators occurs for $x=q+1$ and is for sufficiently large $q$ an embedded subgeometry.     

On the classification of linear complementary dual codes

We give a complete classification of binary linear complementary dual codes of lengths up to 13 and ternary linear complementary dual codes of lengths up to 10.     

On circular–linear one-factorizations of the complete graph

In Korchmáros et al. (2018)one-factorizations of the complete graph $K_n$ are constructed for $n=q+1$ with any odd prime power $q$ such that either $q\equiv 1(mod4)$ or $q=2^h?1$. The arithmetic restriction $n=q+1$ is due to the fact that the vertices of $K_n$ in the construction are the points of a conic $\Omega$ in the finite plane of order $q$. Here we work on the Euclidean plane and describe an analogous construction where the role of $\Omega$ is taken by a regular $n$-gon. This allows us to remove the above constraints and construct one-factorizations of $K_n$ for every even $n\ge 6$.     

On the robust hardness of Gröbner basis computation

The computation of Gröbner bases is an established hard problem. By contrast with many other problems, however, there has been little investigation of whether this hardness is robust. In this paper, we frame and present results on the problem of approximate computation of Gröbner bases. We show that it is NP-hard to construct a Gröbner basis of the ideal generated by a set of polynomials, even when the algorithm is allowed to discard a $1??$ fraction of the generators, and likewise when the algorithm is allowed to discard variables (and the generators containing them). Our results show that computation of Gröbner bases is robustly hard even for simple polynomial systems (e.g. maximum degree 2, with at most 3 variables per generator). We conclude by greatly strengthening results for the Strong c-Partial Gröbner problem posed by De Loera et al. [10]. Our proofs also establish interesting connections between the robust hardness of Gröbner bases and that of SAT variants and graph-coloring.     

On the integrability of Degasperis–Procesi equation: Control of the Sobolev norms and Birkhoff resonances

We consider the dispersive Degasperis–Procesi equation $u_t?u_{xxt}?\mathtt{c}{u}_{xxx}+4\mathtt{c}{u}_x?u{u}_{xxx}?3u_x{u}_{xx}+4u{u}_x=0$ with $\mathtt{c}\in \mathbb{R}?\{0\}$. In [15] the authors proved that this equation possesses infinitely many conserved quantities. We prove that there are infinitely many of such constants of motion which control the Sobolev norms and which are analytic in a neighborhood of the origin of the Sobolev space $H^s$ with $s\ge 2$, both on $\mathbb{R}$ and $\mathbb{T}$. By the analysis of these conserved quantities we deduce a result of global well-posedness for solutions with small initial data and we show that, on the circle, the formal Birkhoff normal form of the Degasperis–Procesi at any order is action-preserving.     

On the number of Waring decompositions for a generic polynomial vector

We prove that a general polynomial vector $(f_1,f_2,f_3)$ in three homogeneous variables of degrees $(3,3,4)$ has a unique Waring decomposition of rank 7. This is the first new case we are aware of, and likely the last one, after five examples known since the 19th century and the binary case. We prove that there are no identifiable cases among pairs $(f_1,f_2)$ in three homogeneous variables of degree $(a,a+1)$, unless $a=2$, and we give a lower bound on the number of decompositions. The new example was discovered with Numerical Algebraic Geometry, while its proof needs Nonabelian Apolarity.