Note sur une caractérisation des graphes dont le degré de déséquilibre est maximal
Dans cette note on démontre la conjecture d'Abelson et Rosenberg sur le degré maximal de déséquilibre d'un graphe à n sommets et on caractérise ces graphes maximaux.
Note: The Smallest Nonevasive Graph Property
A property of n-vertex graphs is called evasive if every algorithm testing this property by asking questions of the form “is there an edge between vertices u and v” requires, in the worst case, to ask about all pairs of vertices. Most “natural” graph properties are either evasive or conjectured to be such, and of the few examples of nontrivial nonevasive properties scattered in the literature the smallest one has n = 6. We exhibit a nontrivial, nonevasive property of 5-vertex graphs and show that...
Notes on nonrepetitive graph colouring.
Notes on sufficient conditions for a graph to be hamiltonian.
Notes on the independence number in the Cartesian product of graphs
Every connected graph G with radius r(G) and independence number α(G) obeys α(G) ≥ r(G). Recently the graphs for which equality holds have been classified. Here we investigate the members of this class that are Cartesian products. We show that for non-trivial graphs G and H, α(G ☐ H) = r(G ☐ H) if and only if one factor is a complete graph on two vertices, and the other is a nontrivial complete graph. We also prove a new (polynomial computable) lower bound α(G ☐ H) ≥ 2r(G)r(H) for the independence...
Nouvelles approches de la propriété (T) de Kazhdan
Un groupe localement compact a la propriété (T) de Kazhdan si la -cohomologie de tout -module hilbertien est nulle. Cette propriété de rigidité de la théorie des représentations de a trouvé des applications qui vont de la théorie ergodique à la théorie des graphes. Pendant près de 30 ans, les seuls exemples connus de groupes avec la propriété (T), provenaient des groupes algébriques simples sur les corps locaux, ou de leurs réseaux. La situation a radicalement changé ces dernières années :...
Nowhere continuous solutions to elliptic systems
Nowhere-zero 3-flows in squares of graphs.
Nowhere-zero -flows of supergraphs.
Nowhere-zero modular edge-graceful graphs
For a connected graph G of order n ≥ 3, let f: E(G) → ℤₙ be an edge labeling of G. The vertex labeling f’: V(G) → ℤₙ induced by f is defined as , where the sum is computed in ℤₙ. If f’ is one-to-one, then f is called a modular edge-graceful labeling and G is a modular edge-graceful graph. A modular edge-graceful labeling f of G is nowhere-zero if f(e) ≠ 0 for all e ∈ E(G) and in this case, G is a nowhere-zero modular edge-graceful graph. It is shown that a connected graph G of order n ≥ 3 is nowhere-zero...
NP-completeness of minimal width unordered tree layout.
NP-hardness results for intersection graphs
Nullity of Graphs
Nullity of Graphs: An Updated Survey
Numerical Procedure for Solving a Minimization Eigenvalue Problem.