Spectral strengthening of a theorem on transversal critical graphs

A transversal set of a graph G is a set of vertices incident to all edges of G. The transversal number of G, denoted by $\tau (G)$, is the minimum cardinality of a transversal set of G. A simple graph G with no isolated vertex is called τ-critical if $\tau (G?e)<\tau (G)$ for every edge $e\in E(G)$. For any τ-critical graph G with $\tau (G)=t$, it has been shown that $|V(G)|\le 2t$ by Erd?s and Gallai and that $|E(G)|\le \left(\begin{array}{c}t+1\\ 2\end{array}\right)$ by Erd?s, Hajnal and Moon. Most recently, it was extended by Gyárfás and Lehel to $|V(G)|+|E(G)|\le \left(\begin{array}{c}t+2\\ 2\end{array}\right)$. In this paper, we prove stronger results via spectrum. Let G be a τ-critical graph with $\tau (G)=t$ and $|V(G)|=n$, and let ${\lambda }_1$ denote the largest eigenvalue of the adjacency matrix of G. We show that $n+{\lambda }_1\le 2t+1$ with equality if and only if G is $t{K}_2$, $K_{s+1}\cup (t?s)K_2$, or $C_{2s?1}\cup (t?s)K_2$, where $2\le s\le t$; and in particular, ${\lambda }_1(G)\le t$ with equality if and only if G is $K_{t+1}$. We then apply it to show that for any nonnegative integer r, we have $n(r+\frac{{\lambda }_1}{2})\le \left(\begin{array}{c}t+r+1\\ 2\end{array}\right)$ and characterize all extremal graphs. This implies a pure combinatorial result that $r|V(G)|+|E(G)|\le \left(\begin{array}{c}t+r+1\\ 2\end{array}\right)$, which is stronger than Erd?s-Hajnal-Moon Theorem and Gyárfás-Lehel Theorem. We also have some other generalizations.     

Stability of attractors for the Kirchhoff wave equation with strong damping and critical nonlinearities

The paper investigates longtime dynamics of the Kirchhoff wave equation with strong damping and critical nonlinearities: $u_{tt}?(1+?{\Vert \mathrm{?}u\Vert }^2)\mathrm{\Delta }u?\mathrm{\Delta }{u}_t+h(u_t)+g(u)=f(x)$, with $?\in [0,1]$. The well-posedness and the existence of global and exponential attractors are established, and the stability of the attractors on the perturbation parameter ? is proved for the IBVP of the equation provided that both nonlinearities $h(s)$ and $g(s)$ are of critical growth.     

On the chromatic number of some P5-free graphs

Let G be a graph. We say that G is perfectly divisible if for each induced subgraph H of G, $V(H)$ can be partitioned into A and B such that $H[A]$ is perfect and $\omega (H[B])<\omega (H)$. We use $P_t$ and $C_t$ to denote a path and a cycle on t vertices, respectively. For two disjoint graphs $F_1$ and $F_2$, we use $F_1\cup F_2$ to denote the graph with vertex set $V(F_1)\cup V(F_2)$ and edge set $E(F_1)\cup E(F_2)$, and use $F_1+F_2$ to denote the graph with vertex set $V(F_1)\cup V(F_2)$ and edge set $E(F_1)\cup E(F_2)\cup \{xy|x\in V(F_1)\text{ and }y\in V(F_2)\}$. In this paper, we prove that (i) $(P_5,C_5,K_{2,3})$-free graphs are perfectly divisible, (ii) $\chi (G)\le 2{\omega }^2(G)?\omega (G)?3$ if G is $(P_5,K_{2,3})$-free with $\omega (G)\ge 2$, (iii) $\chi (G)\le \frac{3}{2}({\omega }^2(G)?\omega (G))$ if G is $(P_5,K_1+2K_2)$-free, and (iv) $\chi (G)\le 3\omega (G)+11$ if G is $(P_5,K_1+(K_1\cup K_3))$-free.     

On bifurcation of eigenvalues along convex symplectic paths

We consider a continuously differentiable curve $t?\gamma (t)$ in the space of $2n\times 2n$ real symplectic matrices, which is the solution of the following ODE:

$\frac{\mathrm{d}\gamma }{\mathrm{d}t}(t)=J_{2n}A(t)\gamma (t),\gamma (0)\in \mathrm{Sp}(2n,\mathbb{R}),$

where $J=J_{2n}\stackrel{\text{def}}{=}\left[\begin{array}{cc}\hfill 0\hfill & \hfill {\mathrm{Id}}_n\hfill \\ \hfill ?{\mathrm{Id}}_n\hfill & \hfill 0\hfill \end{array}\right]$ and $A:t?A(t)$ is a continuous path in the space of $2n\times 2n$ real matrices which are symmetric. Under a certain convexity assumption (which includes the particular case that $A(t)$ is strictly positive definite for all $t\in \mathbb{R}$), we investigate the dynamics of the eigenvalues of $\gamma (t)$ when t varies, which are closely related to the stability of such Hamiltonian dynamical systems. We rigorously prove the qualitative behavior of the branching of eigenvalues and explicitly give the first order asymptotics of the eigenvalues. This generalizes classical Krein–Lyubarskii theorem on the analytic bifurcation of the Floquet multipliers under a linear perturbation of the Hamiltonian. As a corollary, we give a rigorous proof of the following statement of Ekeland: $\{t\in \mathbb{R}:\gamma (t)\text{ has a Krein indefinite eigenvalue of modulus }1\}$ is a discrete set.     

Ramsey number of multiple copies of stars

Let G and H be simple graphs. The Ramsey number $r(G,H)$ is the minimum integer N such that any red-blue-coloring of edges of $K_N$ contains either a red copy of G or a blue copy of H. Let $m{K}_{1,t}$ denote m vertex-disjoint copies of $K_{1,t}$. A lower bound is that $r(m{K}_{1,t},n{K}_{1,s})\ge m(t+1)+n?1$. Burr, Erd?s and Spencer proved that this bound is indeed the Ramsey number $r(m{K}_{1,t},n{K}_{1,s})$ for $t=s=3$, $m\ge 2$ and $m\ge n$. In this paper, we show that this bound is the Ramsey number $r(m{K}_{1,t},n{K}_{1,s})$ for $t\ge s=3,m\ge 2$ and $m\ge n$. We also show that this bound is the Ramsey number $r(m{K}_{1,t},n{K}_{1,s})$ for $s\ge 4,t>\frac{s(s?1)}{2}$ and $m>n$.     

Local boundedness of solutions to non-local parabolic equations modeled on the fractional p-Laplacian

We state and prove estimates for the local boundedness of subsolutions of non-local, possibly degenerate, parabolic integro-differential equations of the form

${?}_{t}u(x,t)+\text{P.V.}\underset{{\mathbb{R}}^n}{\int }K(x,y,t)|u(x,t)?u(y,t){|}^{p?2}(u(x,t)?u(y,t))dy=0,$

$(x,t)\in {\mathbb{R}}^n\times \mathbb{R}$, where P.V. means in the principle value sense, $p\in (1,\infty )$ and the kernel obeys $K(x,y,t)\approx |x?y{|}^{n+ps}$ for some $s\in (0,1)$, uniformly in $(x,y,t)\in {\mathbb{R}}^n\times {\mathbb{R}}^n\times \mathbb{R}$.     

Point partition numbers: Decomposable and indecomposable critical graphs

Graphs considered in this paper are finite, undirected and loopless, but we allow multiple edges. The point partition number ${\chi }_t(G)$ is the least integer k for which G admits a coloring with k colors such that each color class induces a $(t?1)$-degenerate subgraph of G. So ${\chi }_1$ is the chromatic number and ${\chi }_2$ is the point arboricity. The point partition number ${\chi }_t$ with $t\ge 1$ was introduced by Lick and White. A graph G is called ${\chi }_t$-critical if every proper subgraph H of G satisfies ${\chi }_t(H)<{\chi }_t(G)$. In this paper we prove that if G is a ${\chi }_t$-critical graph whose order satisfies $|G|\le 2{\chi }_t(G)?2$, then G can be obtained from two non-empty disjoint subgraphs $G_1$ and $G_2$ by adding t edges between any pair $u,v$ of vertices with $u\in V(G_1)$ and $v\in V(G_2)$. Based on this result we establish the minimum number of edges possible in a ${\chi }_t$-critical graph G of order n and with ${\chi }_t(G)=k$, provided that $n\le 2k?1$ and t is even. For $t=1$ the corresponding two results were obtained in 1963 by Tibor Gallai.     

Long time behavior of solutions to the 3D Hall-magneto-hydrodynamics system with one diffusion

This paper studies the asymptotic behavior of smooth solutions to the generalized Hall-magneto-hydrodynamics system (1.1) with one single diffusion on the whole space ${\mathbb{R}}^3$. We establish that, in the inviscid resistive case, the energy ${6b(t)6}_2^2$ vanishes and ${6u(t)6}_2^2$ converges to a constant as time tends to infinity provided the velocity is bounded in $W^{1?\alpha ,\frac{3}{\alpha }}({\mathbb{R}}^3)$; in the viscous non-resistive case, the energy ${6u(t)6}_2^2$ vanishes and ${6b(t)6}_2^2$ converges to a constant provided the magnetic field is bounded in $W^{1?\beta ,\infty }({\mathbb{R}}^3)$. In summary, one single diffusion, being as weak as ${(?\mathrm{\Delta })}^{\alpha }b$ or ${(?\mathrm{\Delta })}^{\beta }u$ with small enough $\alpha ,\beta$, is sufficient to prevent asymptotic energy oscillations for certain smooth solutions to the system.