3-Restricted arc connectivity of digraphs

The $k$-restricted arc connectivity of digraphs is a common generalization of the arc connectivity and the restricted arc connectivity. An arc subset $S$ of a strong digraph $D$ is a $k$-restricted arc cut if $D?S$ has a strong component $D^{\prime }$ with order at least $k$ such that $D?V\left(D^{\prime }\right)$ contains a connected subdigraph with order at least $k$. The $k$-restricted arc connectivity ${\lambda }^k\left(D\right)$ of a digraph $D$ is the minimum cardinality over all $k$-restricted arc cuts of $D$.Let $D$ be a strong digraph with order $n\ge 6$ and minimum degree $\delta \left(D\right)$. In this paper, we first show that ${\lambda }^3\left(D\right)$ exists if $\delta \left(D\right)\ge 3$ and, furthermore, ${\lambda }^3\left(D\right)\le {\xi }^3\left(D\right)$ if $\delta \left(D\right)\ge 4$, where ${\xi }^3\left(D\right)$ is the minimum 3-degree of $D$. Next, we prove that ${\lambda }^3\left(D\right)={\xi }^3\left(D\right)$ if $\delta \left(D\right)\ge \frac{n+3}{2}$. Finally, we give examples showing that these results are best possible in some sense.     

General convergence analysis for two-step projection methods and applications to variational problems

First a general model for two-step projection methods is introduced and second it has been applied to the approximation solvability of a system of nonlinear variational inequality problems in a Hilbert space setting. Let $H$ be a real Hilbert space and $K$ be a nonempty closed convex subset of $H$. For arbitrarily chosen initial points $x^0,y^0\in K$, compute sequences $\left\{x^k\right\}$ and $\left\{y^k\right\}$ such that $x^{k+1}=(1-a^k)x^k+a^k{P}_K[y^k-\rho T\left(y^k\right)]\text{for }\rho >0$$y^k=(1-b^k)x^k+b^k{P}_K[x^k-\eta T\left(x^k\right)]\text{for }\eta >0\text{,}$ where $T:K\to H$ is a nonlinear mapping on $K,P_K$ is the projection of $H$ onto $K$, and $0\le a^k,b^k\le 1$. The two-step model is applied to some variational inequality problems.     

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.     

Vertex disjoint 4-cycles in bipartite tournaments

Let $k\ge 2$ be an integer. Bermond and Thomassen conjectured that every digraph with minimum out-degree at least $2k?1$ contains $k$ vertex-disjoint cycles. Recently Bai, Li and Li proved this conjecture for bipartite digraphs. In this paper we prove that every bipartite tournament with minimum out-degree at least $2k?2$, minimum in-degree at least $1$ and partite sets of cardinality at least $2k$ contains $k$ vertex-disjoint 4-cycles whenever $k\ge 3$. Finally, we show that every bipartite tournament with minimum degree $\delta =min\{{\delta }^{+},{\delta }^{?}\}$ at least $1.5k?1$ contains at least $k$ vertex-disjoint 4-cycles.     

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

Descendant sets in infinite,primitive highly arc transitive digraphs with prime power out-valency

The descendant set $\mathrm{desc}\left(\alpha \right)$ of a vertex $\alpha$ in a directed graph (digraph) is the subdigraph on the set of vertices reachable by a directed path from $\alpha$. We study the structure of descendant sets $\Gamma$ in an infinite, primitive, highly arc transitive digraph with out-valency $p^k$, where $p$ is a prime and $k\ge 1$. It was already known that $\Gamma$ is a tree when $k=1$ and we show the same holds when $k=2$. However, for $k\ge 3$ there are examples of infinite, primitive highly arc transitive digraphs of out-valency $p^k$ whose descendant sets are not trees, for some prime $p$.     

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

Improved FPT algorithms for weighted independent set in bull-free graphs

Very recently, Thomassé et al. (2017) have given an FPT algorithm for Weighted Independent Set in bull-free graphs parameterized by the weight of the solution, running in time $2^{O\left(k^5\right)}?n^9$. In this article we improve this running time to $2^{O\left(k^2\right)}?n^7$. As a byproduct, we also improve the previous Turing-kernel for this problem from $O\left(k^5\right)$ to $O\left(k^2\right)$. Furthermore, for the subclass of bull-free graphs without holes of length at most $2p?1$ for $p\ge 3$, we speed up the running time to $2^{O(k?k^{\frac{1}{p?1}})}?n^7$. As $p$ grows, this running time is asymptotically tight in terms of $k$, since we prove that for each integer $p\ge 3$, Weighted Independent Set cannot be solved in time $2^{o\left(k\right)}?n^{O\left(1\right)}$ in the class of $\{\text{bull},C_4,\dots ,C_{2p?1}\}$-free graphs unless the ETH fails.     

Quadratic obstructions to small-time local controllability for scalar-input systems

We consider nonlinear finite-dimensional scalar-input control systems in the vicinity of an equilibrium.When the linearized system is controllable, the nonlinear system is smoothly small-time locally controllable: whatever $m>0$ and $T>0$, the state can reach a whole neighborhood of the equilibrium at time T with controls arbitrary small in $C^m$-norm.When the linearized system is not controllable, we prove that: either the state is constrained to live within a smooth strict manifold, up to a cubic residual, or the quadratic order adds a signed drift with respect to it. This drift holds along a Lie bracket of length $(2k+1)$, is quantified in terms of an $H^{?k}$-norm of the control, holds for controls small in $W^{2k,\infty }$-norm and these spaces are optimal. Our proof requires only $C^3$ regularity of the vector field.This work underlines the importance of the norm used in the smallness assumption on the control, even in finite dimension.     

The Laplacian spectral radius of trees and maximum vertex degree

Let $\Delta \left(T\right)$ and $\mu \left(T\right)$ denote the maximum degree and the Laplacian spectral radius of a tree $T$, respectively. In this paper we prove that for two trees $T_1$ and $T_2$ on $n(n\ge 21)$ vertices, if $\Delta \left(T_1\right)>\Delta \left(T_2\right)$ and $\Delta \left(T_1\right)\ge ?\frac{11n}{30}?+1$, then $\mu \left(T_1\right)>\mu \left(T_2\right)$, and the bound “$\Delta \left(T_1\right)\ge ?\frac{11n}{30}?+1$” is the best possible. We also prove that for two trees $T_1$ and $T_2$ on $2k(k\ge 4)$ vertices with perfect matchings, if $\Delta \left(T_1\right)>\Delta \left(T_2\right)$ and $\Delta \left(T_1\right)\ge ?\frac{k}{2}?+2$, then $\mu \left(T_1\right)>\mu \left(T_2\right)$.