Graphes orientes indécomposables en circuits hamiltoniens

Let G be a cubic graph of order 2n consisting of a cycle plus a perfect matching and let $\text{G}{}^1$ be the symmetric digraph obtained from G by replacing each edge of G by two opposite arcs. In this paper we study when $\text{G}{}^1$ can be decomposed into three hamiltonian circuits and in particular we prove that such a decomposition is impossible if n is even.     

Graphs without quadrilaterals

Let f(n) denote the maximum number of edges of a graph on n vertices not containing a circuit of length 4. It is well known that $\text{f(n) ～}\text{1}\text{2}\text{n}\text{n}$. The old conjecture $\text{f(q}{}^2\text{+ q + 1) =}\text{1}\text{2}\text{q(q + 1)}{}^2$ is proved for infinitely many q (whenever q = 2^k).     

Further results on graph equations for line graphs and n-th power graphs

We present solutions of seven graph equations involving the line graph, complement and n-th power operations. One such equation $\text{L(G)}{}^{\mathrm{n}}\text{=}\text{G}\text{?}$ generalizes a result of M. Aigner. In addition, some comments are made about graphs satisfying $\text{G}{}^{\mathrm{n}}\text{=}\text{G}\text{?}$.     

Some properties of irreducible coverings by cliques of complete multipartite graphs

In this paper some recursion formulas and asymptotic properties are derived for the numbers, denoted by N(p, q), of irreducible coverings by edges of the vertices of complete bipartite (labeled) graphs K_p,q. The problem of determining numbers N(p, q) has been raised by I. Tomescu (dans “Logique, Automatique, Informatique,” pp. 269–423, Ed. Acad. R.S.R., Bucharest, 1971). A result concerning the asymptotic behavior of the number of irreducible coverings by cliques of q-partite complete graphs is obtained and it is proved that , $\text{lim}{}_{\mathrm{n\to \infty }}\text{(}\text{log}\text{M(n))}{}^{\mathrm{<mtext>1</mtext><mtext>n</mtext>}}\text{= 3}{}^{\mathrm{<mtext>1</mtext><mtext>3</mtext>}}$, and $\text{lim}{}_{\mathrm{n\to \infty }}\text{C(n)}{}^{\mathrm{<mtext>1</mtext><mtext>n</mtext>}}\text{(}\text{n}\text{ln}\text{n)}\text{=}\text{1}\text{e}$, where I(n) and M(n) are the maximal numbers of irreducible coverings, respectively, coverings by cliques of the vertices of an n-vertex graph, and C(n) is the maximal number of minimal colorings of an n-vertex graph. It is also shown that maximal number of irreducible coverings by n ? 2 cliques of the vertices of an n-vertex graph (n ≥ 4) is equal to 2^n?2 ? 2 and this number of coverings is attained only for K_2,n?2 and the value of $\text{lim}{}_{\mathrm{n\to \infty }}\text{I(n, n ? k)}{}^{\mathrm{<mtext>1</mtext><mtext>n</mtext>}}$ is obtained, where I(n, n ? k) denotes the maximal number of irreducible coverings of an n-vertex graph by n ? k cliques.     

Spheres tangent to all the faces of a simplex

There are at most 2ⁿ spheres tangent to all n + 1 faces of an n-simplex. It has been shown that the minimum number of such spheres is $\text{2}{}^{\mathrm{n}}\text{? c(n,}\text{1}\text{2}\text{(n + 1))}$ if n is odd and $\text{2}{}^{\mathrm{n}}\text{? c(n,}\text{1}\text{2}\text{(n + 1))}$ if n is even. The object of this note is to show that this result is a consequence of a theorem in graph theory.     

Factorizing the complete graph into factors with large star number

The graph G has star number n if any n vertices of G belong to a subgraph which is a star. Let f(n, k) be the smallest number m such that the complete graph on m vertices can be factorized into k factors with star number n. In the present paper we prove that $\text{c}{}_1{}^{\mathrm{n}}\text{k ≤ f(n, k) < c}{}_2{}^{\mathrm{n}}\text{k}$.     

Vertex degrees of planar graphs

Let G be a planar graph having n vertices with vertex degrees d₁, d₂,…,d_n. It is shown that $\text{Σ}{}_{\mathrm{i=1}}{}^{\mathrm{n}}\text{d}{}_{\mathrm{i}}{}^2\text{≤ 2n}{}^2\text{+ O(n)}$. The main term in this upper bound is best possible.     

Further results on the Aanderaa-Rosenberg conjecture

Some results on the “evasiveness” of graph properties are obtained, extending the work of Rivest and Vuillemin. In particular, it is shown that any nontrivial monotone graph property on n vertices is at least $\text{n}{}^2\text{9}\text{-}\text{evasive}$; particular stronger results are obtained for values of n that are powers of primes less than 14. A new result allowing interpolation among n values is obtained, as are some stronger results on restricted classes of properties.     

Fast algorithms for generating all maximal independent sets of interval,circular-arc and chordal graphs

In this paper we give fast algorithms for generating all maximal independent sets of three special classes of graphs—interval, circular-arc, and chordal graphs. The worst-case running times of our algorithms are O(n² + β) for interval and circular-arc graphs, and $\text{O((n + e)}{}^1\text{α)}$ for chordal graphs, where n, e, and α are the numbers of vertexes, edges, and maximal independent sets of a graph, and β is the sum of the numbers of vertexes of all maximal independent sets. Our algorithms compare favorably with the fastest known algorithm for general graphs which has a worst-case running time of $\text{O(n}{}^1\text{e}{}^1\text{α)}$.     

On the maximum cardinality of a consistent set of arcs in a random tournament

For any tournament T on n vertices, let h(T) denote the maximum number of edges in the intersection of T with a transitive tournament on the same vertex set. Sharpening a previous result of Spencer, it is proved that, if T_n denotes the random tournament on n vertices, then, $\text{P}$$\text{(h(T}{}_{\mathrm{n}}\text{) ≤}\text{1}\text{2}\text{(}{}_2{}^{\mathrm{n}}\text{) + 1.73n}{}^{\mathrm{<mtext>3</mtext><mtext>2</mtext>}}\text{) → 1}$ as n → ∞.     

An exact threshold theorem for random graphs and the node-packing problem

The usual linear relaxation of the node-packing problem contains no useful information when the underlying graph G has the property of “bicriticality.” We consider a sparse random graph G_n(m) obtained in the usual way from a random directed graph with fixed out-degree m and show that the probability that G_n(2) is bicritical tends to $\text{(1−2e}{}^{\mathrm{-2}}\text{)}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}$ as n→∞. This confirms a conjecture by G. R. Grimmett and W. R. Pulleyblank (Oper. Res. Lett., in press).     

A theoretical analysis of backtracking in the graph coloring problem

The graph coloring problem is: Given a positive integer K and a graph G. Can the vertices of G be properly colored in K colors? The problem is NP-complete. The average behavior of the simplest backtrack algorithm for this problem is studied. Average run time over all graphs is known to be bounded. Average run time over all graphs with n vertices and q edges behaves like $\text{exp}\text{(}\text{Cn}{}^2\text{q}\text{)}$. It is shown that similar results hold for all higher moments of the run time distribution. For all graphs and for graphs where lim $\text{n}{}^2\text{q}$ exists, the run time has a limiting disibution as n → ∞.     

Second-order optimality of randomized estimation and test procedures

Let P_{(Θ, τ)} 6 $\text{A}$, θ ∈ Θ ? $\text{R}$, τ ∈ T ? $\text{R}$^p denote a family of probability measures, where τ denotes the vector of nuisance parameters. Starting from randomized asymptotic maximum likelihood (as. m. l.) estimators for (θ, τ) we construct randomized estimators which are asymptotically median unbiased up to $\text{o(n}{}^{\mathrm{<mtext>?1</mtext><mtext>2</mtext>}}\text{)}$ resp. test procedures which are as. similar of level $\text{α + o(n}{}^{\mathrm{<mtext>?1</mtext><mtext>2</mtext>}}\text{)}$ (for testing θ = θ₀, τ ∈ T against one sided alternatives). The estimation procedures are second-order efficient in the class of estimators which are median unbiased up to $\text{o(n}{}^{\mathrm{<mtext>?1</mtext><mtext>2</mtext>}}\text{)}$ and the test procedures are second-order efficient in the class of tests which are as. of level $\text{α + o(n}{}^{\mathrm{<mtext>?1</mtext><mtext>2</mtext>}}\text{)}$. These results hold without any continuity condition on the family of probability measures.     

Sharp Sobolev type inequalities for higher fractional derivativesInégalités optimales de type Sobolev pour les dérivées fractionelles d'ordre supérieur

On $\text{R}{}^{\mathrm{n}}$, n?1 and n≠2, we prove the existence of a sharp constant for Sobolev inequalities with higher fractional derivatives. Let s be a positive real number. For n>2s and $\text{q=}\text{2n}\text{n?2s}$ any function $\text{f∈}\text{H}{}^{\mathrm{s}}\text{(}\text{R}{}^{\mathrm{n}}\text{)}$ satisfies

$\text{6f6}{}^2{}_{\mathrm{q}}\text{?S}{}_{\mathrm{n,s}}\text{(?Δ)}{}^{\mathrm{s/2}}\text{f}{}^2{}_2\text{,}$

where the operator (?Δ)^s in Fourier spaces is defined by $\text{(?Δ)}{}^{\mathrm{s}}\text{f}\text{(k):=(2π|k|)}{}^{\mathrm{2s}}\text{f}\text{(k)}$. To cite this article: A. Cotsiolis, N.C. Tavoularis, C. R. Acad. Sci. Paris, Ser. I 335 (2002) 801–804.     

Sobolev inequalities with remainder terms

The usual Sobolev inequality in $\text{R}$ⁿ, n ? 3, asserts that , with S_n being the sharp constant. This paper is concerned, instead, with functions restricted to bounded domains Ω ? $\text{R}$ⁿ. Two kinds of inequalities are established: (i) If ? = 0 on ?Ω, then with $\text{p =}\text{2}{}^1\text{2}$ and with $\text{q =}\text{n}\text{(n ? 1)}$. (ii) If ? ≠ 0 on ?Ω, then with $\text{q =}\text{2(n ? 1)}\text{(n ? 2)}$. Some further results and open problems in this area are also presented.     

An inequality involving permanents of certain direct products

Let A denote a decomposable symmetric complex valued n-linear function on C^m. We prove

$\text{6A·A6}{}^2\text{?2}{}^{\mathrm{n}}\text{2n}\text{n}{}^{\mathrm{?1}}\text{6A?A6}{}^2$

, where · denotes the symmetric product and ? the tensor product. As a consequence we have per

$\text{M}\text{M}\text{M}\text{M}\text{?2}{}^{\mathrm{n}}\text{[per(M)]}{}^2$

, where M is a positive semidefinite Hermitian matrix and per denotes the permanent function. A sufficient condition for equality in the matrix inequality is that M is a nonnegative diagonal matrix.     

Lower bounds for combinatorial problems on graphs

Nontrivial lower bounds are given for the computation time of various combinatorial problems on graphs under a linear or algebraic decision tree model. An $\text{Ω(n}{}^3\text{log}\text{n)}$ bound is obtained for a “travelling salesman problem” on a weighted complete graph of n vertices. Moreover it is shown that the same bound is valid for the “subgraph detection problem” with respect to property P if P is hereditary and determined by components. Thus an $\text{Ω(n}{}^3\text{log}\text{n)}$ bound is established in a unified way for a rather large class of problems.     

Topological cliques of random graphs

Given a graph G, denote by tcl(G) the largest integer r for which G contains a TK^r, a toplogical complete r-graph. We show that for every ? > 0 almost every graph G of order n satisfies

$\text{(2?ε)n}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}\text{?}\text{tlc}\text{(G)?(2+ε)}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}$

     

Sur les proportions respectives de triangles uni,bi ou tricolores dans un tricoloriage des arêtes du n-emble

On determine le nombre maximum de triangles bicolores quand n tend vers l'infini, soit $\text{24}\text{25}\text{(}{}^{\mathrm{n}}{}_3\text{)+O(n}{}^2\text{)}$. On prouve aussi que, pour n assez grand, plus d'un triangle sur vingt-neuf est unicolore le methode suivie est susceptible de constituer une approche du probléme posé par une conjecture d'Erdos. Sos et Turan sur le nombre maximum de triangles tricolores.