Le probleme d'etoiles pour graphes est np-complet

Nous appelons problème de ‘recollement de voisinages’ (RV) (‘star problem’ ou ‘problème d'ètoiles’) le problème qui consiste à savoir, étant donnée une famille $\text{V}$ de parties d'un ensemble S, s'il existe un graphe (non orienté et sans boucle) dont la famille de voisinages coïncide avec $\text{V}$. L'objectif de cet article est de montrer que le problème RV est NP-complet. La preuve s'appuiera sur l'èquivalence entre RV et le probléme de trouver un automorphisme d'ordre 2 dans un graphe quelconque (AUT2). La NP-complétude de AUT2 a été démontrée par Anna Lubiw [5].     

Sur le joint d'une famille de graphes

Les graphes envisagés dans cet article sont non orientés, sans boucles ni arês multiples. On désigne par X(G) et E(G) les ensembles de sommets et d'arêtes d'un graphe G; ces ensembles seront toujours finis. Les notations usuelles sont ceiles de Berge [1].Dans [5], Zykov introduit la notion de graphe joint de deux graphes donnés. Une propriété du joint de deux graphes dont l'un est réduit à un sommet est donnée dans [3]; c'est une étude plus générate et systématique que nous présentons ici.     

Un probleme de partition de l'ensemble des parties a trois elements d'un ensemble fini

Let X be a set of n elements. Let $\text{T}$₃(X) be the set of all triples of X. We define a clique as a set of triples which intersect pairwise in two elements. In this paper we prove that if n?6, the minimum cardinality of a partition of $\text{T}$₃(X) into cliques is $\text{[}\text{1}\text{4}\text{(n?1)}{}^2\text{]}$.     

Codes projectifs a deux ou trois poids associfs aux hyperquadriques d'une geometrie finie

The notion of closure structures of finite rank is introduced and several closure structures familiar from algebra and logic are shown to be of finite rank. The following theorem is established: Let k be any natural number and $\text{C}$ any closure structure of rank k + 2. If B is a finite base (generating set) of $\text{C}$and D is an irredundant (independent) base of $\text{C}$ such that |B| + k < |D|, then there is an irredundant base E of $\text{C}$ such that |B| < |E| < |B| + k.     

Hypergraphes de chaines d'aretes d'un arbre

We introduce the ‘edges-paths hypergraph of a tree’ and study relations of this notion with graphic geometries, chordable graphs. As particular case, we give a simple characterization of intervals hypergraphs.     

Sur les extensions lineaires d'une famille particuliere d'ordres partiels

Corners are defined as ideals of an ordered integer half-dihedron; the paper develops a method of enumeration of the linear extensions of a given corner by means of an alternating sum of products of trinomials. The main result substantially generalizes previously known results and is by itself the starting point of generalizations to some further ordered sets.     

Une condition suffisante d'existence d'un circuit hamiltonien dans un graphe oriente

In this article we prove that a sufficient condition for an oriented strongly connected graph with n vertices to be Hamiltonian is: (1) for any two nonadjacent vertices x and y

$\text{d}{}^{\mathrm{+}}\text{(x)+d}{}^{\mathrm{?}}\text{(x)+d}{}^{\mathrm{+}}\text{(y)+d}{}^{\mathrm{?}}\text{(y)?sn?1}$

.     

Isomorphismes d'hypergraphes par intersections équicardinales d'arêtes et configurations exclues

In this note we characterize isomorphism between two hypergraphs by means of equicardinality of certain edge intersections and the exclusion of certain pairs of subhypergraphs. Our result is slightly stronger than Theorem 3 of C. Berge and R. Rado (J. Combinatorial Theory Ser. B13 (1972), 226–241) in particular in that isolated vertices are admitted. As a corollary we obtain a result due to J.-L. Paillet.     

Nombre chromatique total d'un hypergraphe

In this paper, the author defines a hypergraph total chromatic number and determines this number for the complete h-partite and for the complete h-uniform hypergraphs.     

Arbres minimaux d'un graphe preordonne

We study the minimal spanning trees of a connected graph G = (X,U) where U is partially preordered (or quasi-ordered). We characterize several kinds of optimal spanning trees and give conditions for existence of strongly optimal trees. Generalizations to bases of matroids (binary matroïds in part 2) are immediate. Sone of our results are given in terms of Krugdahl's dependence graphs. They imply previous results of Rosenstiehl and Gale in the case of linear orders or preorders.     

Polytope des independants d'un graphe serie-parallele

A graph is said to be serie-parallel if it doesn't contain an homeomorph to K₄. The aim of the paper is the demonstration of Chvatal's conjecture on the polytope of independent set of vertices in such graphs. This is done classically by using LP-duality, the algorithm for constructing the primal-dual solution having the nice property to be linear in the number of vertices.     

Petites valeurs de la fonction d'Euler

Let φ be the Euler's function. A question of Rosser and Schoenfeld is answered, showing that there exists infinitely many n such that $\text{n}\text{φ(n)}\text{> e}{}^{\mathrm{y}}\text{log log}\text{n}$, where γ is the Euler's constant. More precisely, if N_k is the product of the first k primes, it is proved that, under the Riemann's hypothesis, $\text{N}{}_{\mathrm{k}}\text{φ(N}{}_{\mathrm{k}}\text{)}\text{> e}{}^{\mathrm{y}}\text{log log}\text{N}{}_{\mathrm{k}}$ holds for any k ≥ 2, and, if the Riemann's hypothesis is false this inequality holds for infinitely many k, and is false for infinitely many k.     

Partitions lineaires arguesiennes d'un espace vectoriel

In this work, we study linear and desarguesian partitions of a finite dimensional vector space over a skew-field K. When K is finite, we describe the set of all these partitions as a homogeneous space of the general linear group and we give an enumeration formula.