On stable cutsets in claw-free graphs and planar graphs

A stable cutset in a connected graph is a stable set whose deletion disconnects the graph. Let $K_4$ and $K_{1,3}$ (claw) denote the complete (bipartite) graph on 4 and $1+3$ vertices. It is NP-complete to decide whether a line graph (hence a claw-free graph) with maximum degree five or a $K_4$-free graph admits a stable cutset. Here we describe algorithms deciding in polynomial time whether a claw-free graph with maximum degree at most four or whether a (claw, $K_4$)-free graph admits a stable cutset. As a by-product we obtain that the stable cutset problem is polynomially solvable for claw-free planar graphs, and also for planar line graphs.Thus, the computational complexity of the stable cutset problem is completely determined for claw-free graphs with respect to degree constraint, and for claw-free planar graphs. Moreover, we prove that the stable cutset problem remains NP-complete for $K_4$-free planar graphs with maximum degree five.     

On a tree-partition problem

If $T=(V,E)$ is a tree then – T denotes the additive hereditary property consisting of all graphs that does not contain T as a subgraph. For an arbitrary vertex v of T we deal with a partition of T into two trees $T_1$, $T_2$, so that $V(T_1)\cap V(T_2)=\{v\}$, $V(T_1)\cup (T_2)=V(T)$, $E(T_1)\cap E(T_2)=\varnothing$, $E(T_1)\cup E(T_2)=E(T)$, $T[V(T_1)\backslash \{v\}]\subseteq E(T_1)$ and $T[V(T_2)\backslash \{v\}]\subseteq E(T_2)$. We call such a partition a $T_v-partition$ of T. We study the following em: Given a graph G belonging to –T. Is it true that for any $T_v$-partition $T_1$, $T_2$ of T there exists a partition $\{V_1,V_2\}$ of the vertices of G such that $G[V_1]\in -T_1$ and $G[V_2]\in -T_2$? This problem provides a natural generalization of Δ-partition problem studied by L. Lovász ([L. Lovász, On decomposition of graphs. Studia Sci. Math. Hungar. 1 (1966) 237–238]) and Path Partition Conjecture formulated by P. Mihók ([P. Mihók, Problem 4, in: M. Borowiecki, Z. Skupien (Eds.), Graphs, Hypergraphs and Matroids, Zielona Góra, 1985, p. 86]). We present some partial results and a contribution to the Path Kernel Conjecture that was formulated with connection to Path Partition Conjecture.     

Greedy approximation for the source location problem with vertex-connectivity requirements in undirected graphs

Let $G=(V,E)$ be a simple undirected graph with a set V of vertices and a set E of edges. Each vertex $v\in V$ has a demand $d(v)\in Z_{+}$, and a cost $c(v)\in R_{+}$, where $Z_{+}$ and $R_{+}$ denote the set of nonnegative integers and the set of nonnegative reals, respectively. The source location problem with vertex-connectivity requirements in a given graph G asks to find a set S of vertices minimizing ${\sum }_{v\in S}c(v)$ such that there are at least $d(v)$ pairwise vertex-disjoint paths from S to v for each vertex $v\in V?S$. It is known that the problem is not approximable within a ratio of $O(\ln {\sum }_{v\in V}d(v))$, unless NP has an $O(N^{\log \log N})$-time deterministic algorithm. Also, it is known that even if every vertex has a uniform cost and $d^1=4$ holds, then the problem is NP-hard, where $d^1=\max \{d(v)|v\in V\}$.In this paper, we consider the problem in the case where every vertex has uniform cost. We propose a simple greedy algorithm for providing a $\max \{d^1,2d^1?6\}$-approximate solution to the problem in $O(\min \{d^1,\sqrt{|V|}\}{d}^1{|V|}^2)$ time, while we also show that there exists an instance for which it provides no better than a $(d^1?1)$-approximate solution. Especially, in the case of $d^1?4$, we give a tight analysis to show that it achieves an approximation ratio of 3. We also show the APX-hardness of the problem even restricted to $d^1?4$.     

Sum choice number of generalized θ-graphs

Let $G=\left(VE\right)$ be a simple graph and for every vertex $v\in V$ let $L\left(v\right)$ be a set (list) of available colors. $G$ is called $L$-colorable if there is a proper coloring $\phi$ of the vertices with $\phi \left(v\right)\in L\left(v\right)$ for all $v\in V$. A function $f:V\to \mathbb{N}$ is called a choice function of $G$ and $G$ is said to be $f$-list colorable if $G$ is $L$-colorable for every list assignment $L$ choice function is defined by $size\left(f\right)={\sum }_{v\in V}f\left(v\right)$ and the sum choice number ${\chi }_{sc}\left(G\right)$ denotes the minimum size of a choice function of $G$.Sum list colorings were introduced by Isaak in 2002 and got a lot of attention since then.For $r\ge 3$ a generalized ${\theta }_{k_1{k}_2\dots k_r}$-graph is a simple graph consisting of two vertices $v_1$ and $v_2$ connected by $r$ internally vertex disjoint paths of lengths $k_1,k_2,\dots ,k_r$ $(k_1\le k_2\le ?\le k_r)$.In 2014, Carraher et al. determined the sum-paintability of all generalized $\theta$-graphs which is an online-version of the sum choice number and consequently an upper bound for it.In this paper we obtain sharp upper bounds for the sum choice number of all generalized $\theta$-graphs with $k_1\ge 2$ and characterize all generalized $\theta$-graphs $G$ which attain the trivial upper bound $\left|V\left(G\right)\right|+\left|E\left(G\right)\right|$.     

On uniqueness of stationary solutions to the Navier–Stokes equations in exterior domains

The aim of this paper is to prove a uniqueness criterion for solutions to the stationary Navier–Stokes equation in 3-dimensional exterior domains within the class $u\in L_{3,\infty }$ with $?u\in L_{3/2,\infty }$, where $L_{3,\infty }$ and $L_{3/2,\infty }$ are the Lorentz spaces. Our criterion asserts that if $u$ and $v$ are the solutions, $u$ is small in $L_{3,\infty }$ and $u,v\in L_p$ for some $p>3$, then $u=v$. The proof is based on analysis of the dual equation with the aid of the bootstrap argument.     

Régularité conditionnelle des équations de Navier–Stokes

In this Note, we give sufficient conditions for the regularity of Leray–Hopf weak solutions to the Navier–Stokes equation. We prove that, if one of three conditions (i) $?u/?x_3\in L_t^{s_0}{L}_x^{r_0}$ where $2/s_0+3/r_0?2$ and $9/4?r_0?3$, (ii) $\mathrm{?}{u}_3\in L_t^{s_1}{L}_x^{r_1}$ where $2/s_1+3/r_1?11/6$ and $54/23?r_0?18/5$, or (iii) $u_3\in L_t^{s_0}{L}_x^{r_0}$ where $2/s_0+3/r_0?5/8$ and $24/5?r_0?\infty$, is satisfied, then the solution is regular. These conditions improve earlier results on the conditional regularity of the Navier–Stokes equations. To cite this article: I. Kukavica, M. Ziane, C. R. Acad. Sci. Paris, Ser. I 343 (2006).     

Deformation of central charges,vertex operator algebras whose Griess algebras are Jordan algebras

If a vertex operator algebra $V={\oplus }_{n=0}^{\infty }{V}_n$ satisfies $\dim V_0=1$, $V_1=0$, then $V_2$ has a commutative (nonassociative) algebra structure called Griess algebra. One of the typical examples of commutative (nonassociative) algebras is a Jordan algebra. For example, the set ${\mathrm{Sym}}_d(\mathbb{C})$ of symmetric matrices of degree d becomes a Jordan algebra. On the other hand, in the theory of vertex operator algebras, central charges influence the properties of vertex operator algebras. In this paper, we construct vertex operator algebras with central charge c and its Griess algebra is isomorphic to ${\mathrm{Sym}}_d(\mathbb{C})$ for any complex number c and a positive integer d.