Graphe distance-transitifEn théorie des graphes, un graphe non-orienté est distance-transitif si pour tous sommets u, v, x, y tels que u et v d'une part et x et y d'autre part sont à même distance, il existe un automorphisme de graphe envoyant u sur x et v sur y. Autrement dit, un graphe est distance-transitif si son groupe d'automorphisme agit transitivement sur chacun des ensembles de paires de sommets à même distance. Tout graphe distance-transitif est distance-régulier.
Graphe trivialement parfaitvignette|upright=2| Construction d'un graphe trivialement parfait à partir d'intervalles imbriqués et de la relation d'accessibilité dans un arbre. En théorie des graphes, un graphe trivialement parfait est un graphe qui a la propriété que dans chacun de ses sous-graphes induits, la taille du stable maximal est égale au nombre de cliques maximales. Les graphes trivialement parfaits ont été étudiés pour la première fois par Elliot S.
Rainbow matchingIn the mathematical discipline of graph theory, a rainbow matching in an edge-colored graph is a matching in which all the edges have distinct colors. Given an edge-colored graph G = (V,E), a rainbow matching M in G is a set of pairwise non-adjacent edges, that is, no two edges share a common vertex, such that all the edges in the set have distinct colors. A maximum rainbow matching is a rainbow matching that contains the largest possible number of edges. Rainbow matchings are of particular interest given their connection to transversals of Latin squares.
Théorème de RamseyEn mathématiques, et plus particulièrement en combinatoire, le théorème de Ramsey, dû à Frank Ramsey (en 1930), est un théorème fondamental de la théorie de Ramsey. Il affirme que pour tout n, tout graphe complet suffisamment grand dont les arêtes sont colorées contient des sous-graphes complets de taille n d'une seule couleur. En théorie des ensembles, une de ses généralisations, le théorème de Ramsey infini, permet de définir un type particulier de grand cardinal.
Théorème de TuránLe théorème de Turán est un résultat de théorie des graphes extrémaux découvert par Pál Turán. Ce théorème donne une borne supérieure sur le nombre d'arêtes dans les graphes ne contenant pas de cliques plus grosses qu'un paramètre r, et donne une caractérisation des graphes atteignant cette borne, ce sont les graphes de Turán. Ce résultat de 1941 a lancé la théorie des graphes extrémaux et possède de nombreuses preuves. Tout graphe G ayant n sommets, et ne contenant pas de clique de taille plus grande que r (i.
Structure d'incidencevignette| Exemples de structures d'incidence: Exemple 1: Points et droites du plan euclidien Exemple 2: Points et cercles Exemple 3: Structure définie par une matrice d'incidence. En mathématiques, une structure d'incidence est toute composition de deux types d'objets dans le plan euclidien : des points ou l'équivalent de points et des droites ou l'équivalent de droites et d'une seule relation possible entre ces types, les autres propriétés étant ignorées et la structure pouvant ainsi se représenter par une matrice.
Graphe de MooreEn théorie des graphes, un graphe de Moore est un graphe régulier dont le nombre de sommets, pour un degré et un diamètre donnés, est maximal. Les graphes de Moore ont été nommés par Alan Hoffman et Robert Singleton en 1960 en hommage à Edward F. Moore, qui avait tenté de décrire et classifier ces graphes. Un graphe de Moore est un graphe régulier de degré d et de diamètre k qui possède un nombre de sommets égal à la borne supérieure : De façon générale, le nombre de sommets d'un graphe de degré maximal d et de diamètre k est inférieur ou égal à cette valeur.
Nombre de croisements (théorie des graphes)vignette| Une représentation du graphe de Heawood avec trois croisements. C'est le nombre minimum de croisements parmi toutes les représentations de ce graphe, qui a donc un nombre de croisements . En théorie des graphes, le nombre de croisements d'un graphe G est le plus petit nombre d'intersections d'arêtes d'un tracé du graphe G. Par exemple, un graphe est planaire si et seulement si son nombre de croisements est nul. La détermination du nombre de croisements tient une place importante dans le tracé de graphes.
