Untangling polygons and graphs

Untangling is a process in which some vertices of a plane graph are moved to obtain a straight-line plane drawing. The aim is to move as few vertices as possible. We present an algorithm that untangles the cycle graph $C_n$ while keeping at least $\mathrm{\Omega }(n^{2/3})$ vertices fixed. For any graph G, we also present an upper bound for the number of fixed vertices in the worst case. The bound is a function of the number of vertices, maximum degree and diameter of G. One of its consequences is the upper bound $O({(n\log n)}^{2/3})$ for all 3-vertex-connected planar graphs.     

Degree Conditions and Degree Bounded Trees

In this paper, we give sufficient conditions for a graph to have degree bounded trees. Let G be a connected graph and $A\subseteq V(G)$. We denote by ${\sigma }_k(A)$ the minimum value of the degree sum in G of any k pairwise nonadjacent vertices of A, and by $w(G-A)$ the number of components of the subgraph $G-A$ of G induced by $V(G)-A$. Our main results are the following: (i) If ${\sigma }_k(A)⩾|G|-1$, then G contains a tree T with maximum degree ⩽k and $A\subseteq V(T)$. (ii) If ${\sigma }_{k-w(G-A)}(A)⩾|A|-1$, then G contains a spanning tree T with $d_T(x)⩽k$ for any $x\in A$. These are generalizations of the result by S. Win [S. Win, Existenz von Gerüsten mit Vorgeschriebenem Maximalgrad in Graphen, Abh. Math. Seminar Univ. Humburg 43 (1975) 263–267] and degree conditions are sharp.     

Extremal trees with given degree sequence for the Randić index

The Randi? index of a graph G is the sum of $((d(u))(d(v)){)}^{\alpha }$ over all edges $\mathit{uv}$ of G, where $d(v)$ denotes the degree of $v$ in G, $\alpha \ne 0$. When $\alpha =1$, it is the weight of a graph. Delorme, Favaron, and Rautenbach characterized the trees with a given degree sequence with maximum weight, where the question of finding the tree that minimizes the weight is left open. In this note, we characterize the extremal trees with given degree sequence for the Randi? index, thus answering the same question for weight. We also provide an algorithm to construct such trees.     

Generating all the Steiner trees and computing Steiner intervals for a fixed number of terminals

In this work we present an enumeration algorithm for the generation of all Steiner trees containing a given set W of terminals of an unweighted graph G such that $|W|=k$, for a fixed positive integer k. The enumeration is performed within $O(n)$ delay, where $n=|V(G)|$ consequence of the algorithm is that the Steiner interval and the strong Steiner interval of a subset $W\subseteq V(G)$ can be computed in polynomial time, provided that the size of W is bounded by a constant.     

Rank,term rank and chromatic number of a graph

Let G be a graph with a nonempty edge set, we denote the rank of the adjacency matrix of G and the term rank of G, by $\mathrm{rk}(G)$ and $\mathrm{Rk}(G)$, respectively. It was conjectured [C. van Nuffelen, Amer. Math. Monthly 83 (1976) 265–266], for any graph G, $\chi (G)?\mathrm{rk}(G)$. The first counterexample to this conjecture was obtained by Alon and Seymour [J. Graph Theor. 13 (1989) 523–525]. Recently, Fishkind and Kotlov [Discrete Math. 250 (2002) 253–257] have proved that for any graph G, $\chi (G)?\mathrm{Rk}(G)$. In this Note we improve Fishkind–Kotlov upper bound and show that $\chi (G)?\frac{\mathrm{rk}(G)+\mathrm{Rk}(G)}{2}$. To cite this article: S. Akbari, H.-R. Fanaï, C. R. Acad. Sci. Paris, Ser. I 340 (2005).     

Self-orthogonal decompositions of graphs into matchings

Given a simple graph H, a self-orthogonal decomposition (SOD) of H is a collection of subgraphs of H, all isomorphic to some graph G, such that every edge of H occurs in exactly two of the subgraphs and any two of the subgraphs share exactly one edge. Our concept of SOD is a natural generalization of the well-studied orthogonal double covers (ODC) of complete graphs. If for some given G there is an appropriate H, then our goal is to find one with as few vertices as possible. Special attention is paid to the case when G a matching with $n-1$ edges. We conjecture that $v(H)=2n-2$ is best possible if $n\ne 4$ is even and $v(H)=2n$ if n is odd. We present a construction which proves this conjecture for all but 4 of the possible residue classes of n modulo 18.     

Parameters of connectivity in (a,b)-linear graphs

For some a and b positive rational numbers, a simple graph with n vertices and $m=an-b$ edges is an $(a,b)$-linear graph, when $n>2b$. We characterize non-empty classes of $(a,b)$-linear graphs and determine those which contain connected graphs. For non-empty classes, we build sequences of $(a,b)$-linear graphs and sequences of connected $(a,b)$-linear graphs. Furthermore, for each of these sequences where every graph is bounded by a constant, we show that its correspondent sequence of diameters diverges, while its correspondent sequence of algebraic connectivities converges to zero.     

Global existence to the initial–boundary value problem for a system of nonlinear diffusion and wave equations

We prove the global existence of weak solution pair to the initial boundary value problem for a system of m-Laplacian type diffusion equation and nonlinear wave equation. The interaction of two equations is given through nonlinear source terms $f(u,v)$ and $g(u,v)$.