Permutations with small maximal k-consecutive sums

Let $n$ and $k$ be positive integers with $n>k$. Given a permutation $({\pi }_1,\dots ,{\pi }_n)$ of integers $1,\dots ,n$, we consider $k$-consecutive sums of $\pi$, i.e., $s_i?{\sum }_{j=0}^{k?1}{\pi }_{i+j}$ for $i=1,\dots ,n$, where we let ${\pi }_{n+j}={\pi }_j$. What we want to do in this paper is to know the exact value of $\mathsf{msum}(n,k)?min\left\{max\{s_i:i=1,\dots ,n\}?\frac{k(n+1)}{2}:\pi \in S_n\right\},$ where $S_n$ denotes the set of all permutations of $1,\dots ,n$. In this paper, we determine the exact values of $\mathsf{msum}(n,k)$ for some particular cases of $n$ and $k$. As a corollary of the results, we obtain $\mathsf{msum}(n,3)$, $\mathsf{msum}(n,4)$ and $\mathsf{msum}(n,6)$ for any $n$.     

Blowup with vorticity control for a 2D model of the Boussinesq equations

We propose a system of equations with nonlocal flux in two space dimensions which is closely modeled after the 2D Boussinesq equations in a hyperbolic flow scenario. Our equations involve a vorticity stretching term and a non-local Biot-Savart law and provide insight into the underlying intrinsic mechanisms of singularity formation. We prove stable, controlled finite time blowup involving upper and lower bounds on the vorticity up to the time of blowup for a wide class of initial data.     

A Hilbert Space Approach to Bounded Analytic Interpolation

We generalize several results on bounded analytic interpolation of Fitzgerald and Horn, which work by majorization by positive definite kernels, to the cases of several complex variables and operator-valued interpolation. Using a lemma of Kolmogorov, we complement a simplification due to Szafraniec in the proofs of the theorems. Received: November 21, 2006. Accepted: August 03, 2007.     

An imbedding property of K-groups

For a pair of rings A⊂B satisfying a certain condition (?) we get general imbedding results for Karoubi-Villamayor, homotopy and Quillen K-theories. One important case is when A and B are respectively the henselization and completion of a regular ring of finite type over a field at a prime ideal.     

Graphs determined by their Aα-spectra

Let $G$ be a graph with $n$ vertices, and let $A\left(G\right)$ and $D\left(G\right)$ denote respectively the adjacency matrix and the degree matrix of $G$. Define $A_{\alpha }\left(G\right)=\alpha D\left(G\right)+(1?\alpha )A\left(G\right)$for any real $\alpha \in [0,1]$. The collection of eigenvalues of $A_{\alpha }\left(G\right)$ together with multiplicities are called the $A_{\alpha }$-spectrum of $G$. A graph $G$ is said to be determined by its $A_{\alpha }$-spectrum if all graphs having the same $A_{\alpha }$-spectrum as $G$ are isomorphic to $G$. We first prove that some graphs are determined by their $A_{\alpha }$-spectra for $0\le \alpha <1$, including the complete graph $K_n$, the union of cycles, the complement of the union of cycles, the union of copies of $K_2$ and $K_1$, the complement of the union of copies of $K_2$ and $K_1$, the path $P_n$, and the complement of $P_n$. Setting $\alpha =0$ or $\frac{1}{2}$, those graphs are determined by $A$- or $Q$-spectra. Secondly, when $G$ is regular, we show that $G$ is determined by its $A_{\alpha }$-spectrum if and only if the join $G\vee K_m$ ($m\ge 2$) is determined by its $A_{\alpha }$-spectrum for $\frac{1}{2}<\alpha <1$. Furthermore, we also show that the join $K_m\vee P_n$ ($m,n\ge 2$) is determined by its $A_{\alpha }$-spectrum for $\frac{1}{2}<\alpha <1$. In the end, we pose some related open problems for future study.     

Corrigendum to “Maximal linear groups induced on the Frattini quotient of a p-group” [J. Pure Appl. Algebra 222 (10) (2018) 2931–2951]

We give a correction to Fig. 1 and supporting text published in the paper: ‘Maximal linear groups induced on the Frattini quotient of a p-group’, J. Pure Appl. Algebra 222 (10) (2018) 2931–2951.     

Graphs with at most one crossing

The crossing number of a graph $G$ is the least number of crossings over all possible drawings of $G$. We present a structural characterization of graphs with crossing number one.     

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

Spanning trees with at most 4 leaves in K1,5-free graphs

In 2009, Kyaw proved that every $n$-vertex connected $K_{1,4}$-free graph $G$ with ${\sigma }_4\left(G\right)\ge n?1$ contains a spanning tree with at most 3 leaves. In this paper, we prove an analogue of Kyaw’s result for connected $K_{1,5}$-free graphs. We show that every $n$-vertex connected $K_{1,5}$-free graph $G$ with ${\sigma }_5\left(G\right)\ge n?1$ contains a spanning tree with at most 4 leaves. Moreover, the degree sum condition “${\sigma }_5\left(G\right)\ge n?1$” is best possible.     

The size of 3-uniform hypergraphs with given matching number and codegree

To determine the size of $r$-graphs with given graph parameters is an interesting problem. Chvátal and Hanson (JCTB, 1976) gave a tight upper bound of the size of 2-graphs with restricted maximum degree and matching number; Khare (DM, 2014) studied the same problem for linear 3-graphs with restricted matching number and maximum degree. In this paper, we give a tight upper bound of the size of 3-graphs with bounded codegree and matching number.     

Connected k-dominating graphs

For a graph $G=(V,E)$, the $k$-dominating graph $D_k\left(G\right)$ of $G$ has vertices corresponding to the dominating sets of $G$ having cardinality at most $k$, where two vertices of $D_k\left(G\right)$ are adjacent if and only if the dominating set corresponding to one of the vertices can be obtained from the dominating set corresponding to the second vertex by the addition or deletion of a single vertex. We denote the domination and upper domination numbers of $G$ by $\gamma \left(G\right)$ and $\Gamma \left(G\right)$, respectively, and the smallest integer $\epsilon$ for which $D_k\left(G\right)$ is connected for all $k\ge \epsilon$ by $d_0\left(G\right)$. It is known that $\Gamma \left(G\right)+1\le d_0\left(G\right)\le \left|V\right|$, but constructing a graph $G$ such that $d_0\left(G\right)>\Gamma \left(G\right)+1$ appears to be difficult.We present two related constructions. The first construction shows that for each integer $k\ge 3$ and each integer $r$ such that $1\le r\le k?1$, there exists a graph $G_{k,r}$ such that $\Gamma \left(G_{k,r}\right)=k$, $\gamma \left(G_{k,r}\right)=r+1$ and $d_0\left(G_{k,r}\right)=k+r=\Gamma \left(G\right)+\gamma \left(G\right)?1$. The second construction shows that for each integer $k\ge 3$ and each integer $r$ such that $1\le r\le k?1$, there exists a graph $Q_{k,r}$ such that $\Gamma \left(Q_{k,r}\right)=k$, $\gamma \left(Q_{k,r}\right)=r$ and $d_0\left(Q_{k,r}\right)=k+r=\Gamma \left(G\right)+\gamma \left(G\right)$.     

Oriented colourings of graphs with maximum degree three and four

We show that any orientation of a graph with maximum degree three has an oriented 9-colouring, and that any orientation of a graph with maximum degree four has an oriented 69-colouring. These results improve the best known upper bounds of 11 and 80, respectively.     

Graphs are (1,Δ+1)-choosable

A graph $G$ is $(k,k^{\prime })$-choosable if the following holds: For any list assignment $L$ which assigns to each vertex $v$ a set $L\left(v\right)$ of $k$ real numbers, and assigns to each edge $e$ a set $L\left(e\right)$ of $k^{\prime }$ real numbers, there is a total weighting $?:V\left(G\right)\cup E\left(G\right)\to R$ such that $?\left(z\right)\in L\left(z\right)$ for $z\in V\cup E$, and ${\sum }_{e\in E\left(u\right)}?\left(e\right)+?\left(u\right)\ne {\sum }_{e\in E\left(v\right)}?\left(e\right)+?\left(v\right)$ for every edge $uv$. This paper proves that if $G$ is a connected graph of maximum degree $\Delta \ge 2$, then $G$ is $(1,\Delta +1)$-choosable.     

Three sphere inequality for second order elliptic equations with coefficients with jump discontinuity

This is a short note to complete the paper appeared in Francini et al. (2016) [4], where a rough version of the classical well known Hadamard three-circle theorem for solution of an elliptic PDE in divergence form has been proved. Precisely, instead of circles, the authors obtain a similar inequality in a more complicated geometry. In this paper we clean the geometry and obtain a generalized version of the three-circle inequality for elliptic equation with coefficients with discontinuity of jump type.     

Relating broadcast independence and independence

An independent broadcast on a connected graph $G$ is a function $f:V\left(G\right)\to {\mathbb{N}}_0$ such that, for every vertex $x$ of $G$, the value $f\left(x\right)$ is at most the eccentricity of $x$ in $G$, and $f\left(x\right)>0$ implies that $f\left(y\right)=0$ for every vertex $y$ of $G$ within distance at most $f\left(x\right)$ from $x$. The broadcast independence number ${\alpha }_b\left(G\right)$ of $G$ is the largest weight $\sum _{x\in V\left(G\right)}f\left(x\right)$ of an independent broadcast $f$ on $G$. Clearly, ${\alpha }_b\left(G\right)$ is at least the independence number $\alpha \left(G\right)$ for every connected graph $G$. Our main result implies ${\alpha }_b\left(G\right)\le 4\alpha \left(G\right)$. We prove a tight inequality and characterize all extremal graphs.     

Choosability with union separation

List coloring generalizes graph coloring by requiring the color of a vertex to be selected from a list of colors specific to that vertex. One refinement of list coloring, called choosability with separation, requires that the intersection of adjacent lists is sufficiently small. We introduce a new refinement, called choosability with union separation, where we require that the union of adjacent lists is sufficiently large. For $t\ge k$, a $(k,t)$-list assignment is a list assignment $L$ where $\left|L\left(v\right)\right|\ge k$ for all vertices $v$ and $|L\left(u\right)\cup L\left(v\right)|\ge t$ for all edges $uv$. A graph is $(k,t)$-choosable if there is a proper coloring for every $(k,t)$-list assignment. We explore this concept through examples of graphs that are not $(k,t)$-choosable, demonstrating sparsity conditions that imply a graph is $(k,t)$-choosable, and proving that all planar graphs are $(3,11)$-choosable and $(4,9)$-choosable.     

Convergence for non-autonomous semidynamical systems with impulses

The present paper deals with impulsive non-autonomous systems with convergence. We show that the structure of the Levinson center of a compact dissipative system is preserved under homomorphism in impulsive convergent systems. Also, we present some criteria of convergence using Lyapunov functions.     

Gorenstein simplices with a given δ-polynomial

To classify the lattice polytopes with a given $\delta$-polynomial is an important open problem in Ehrhart theory. A complete classification of the Gorenstein simplices whose normalized volumes are prime integers is known. In particular, their $\delta$-polynomials are of the form $1+t^k+?+t^{(v?1)k}$, where $k$ and $v$ are positive integers. In the present paper, a complete classification of the Gorenstein simplices with the above $\delta$-polynomials will be performed, when $v$ is either $p^2$ or $pq$, where $p$ and $q$ are prime integers with $p\ne q$. Moreover, we consider the number of Gorenstein simplices, up to unimodular equivalence, with the expected $\delta$-polynomial.     

Two disjoint shortest paths problem with non-negative edge length

In the two disjoint shortest paths problem ( 2-DSPP), the input is a graph (or a digraph) and its vertex pairs $(s_1,t_1)$ and $(s_2,t_2)$, and the objective is to find two vertex-disjoint paths $P_1$ and $P_2$ such that $P_i$ is a shortest path from $s_i$ to $t_i$ for $i=1,2$, if they exist. In this paper, we give a first polynomial-time algorithm for the undirected version of the 2-DSPP with an arbitrary non-negative edge length function.