Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
9519625 | Comptes Rendus Mathematique | 2005 | 4 Pages |
Abstract
Soit G un graphe avec un ensemble d'arête non vide. On note rk(G) le rang (réel) d'une matrice d'adjacence A de G et Rk(G) le rang maximal d'une matrice ayant même support que A. Il a été conjecturé [C. van Nuffelen, Amer. Math. Monthly 83 (1976) 265-266] que pour tout graphe G, Ï(G)⩽rk(G). Le premier contre-exemple à cette conjecture a été obtenu par Alon et Seymour [J. Graph Theor. 13 (1989) 523-525]. Récemment, Fishkind et Kotlov [Discrete Math. 250 (2002) 253-257] ont montré que pour tout graphe G, Ï(G)⩽Rk(G). Dans cette Note, nous améliorons cette borne et montrons Ï(G)⩽rk(G)+Rk(G)2. Pour citer cet article : S. Akbari, H.-R. Fanaï, C. R. Acad. Sci. Paris, Ser. I 340 (2005).
Related Topics
Physical Sciences and Engineering
Mathematics
Mathematics (General)
Authors
Saieed Akbari, Hamid-Reza Fanaï,