Graphe de ShrikhandeLe graphe de Shrikhande est, en théorie des graphes, un graphe 6-régulier possédant 16 sommets et 48 arêtes, découvert par S. S. Shrikhande. Le diamètre du graphe de Shrikhande, l'excentricité maximale de ses sommets, est 2, son rayon, l'excentricité minimale de ses sommets, est 2 et sa maille, la longueur de son plus court cycle, est 3. Il s'agit d'un graphe 6-sommet-connexe et d'un graphe 6-arête-connexe, c'est-à-dire qu'il est connexe et que pour le rendre déconnecté il faut le priver au minimum de 6 sommets ou de 6 arêtes.
Graphe couronneEn théorie des graphes, une branche des mathématiques, un graphe couronne à 2 n sommets est un graphe non orienté comportant deux jeux de sommets ui et vi reliés par une arête de ui à vj à chaque fois que i ≠ j. Le graphe couronne à six sommets est un graphe cycle. Le graphe couronne à huit sommets est le graphe hexaédrique, celui qui décrit les sommets et les arêtes d'un cube. Le graphe couronne peut être vu comme un graphe biparti complet d'où l'on aurait retiré les arêtes formant un couplage parfait (les arêtes horizontales absentes sur la figure).
Graphe de PaleyEn théorie des graphes, un graphe de Paley est un graphe dense et non orienté. Ses sommets sont les éléments d'un corps fini, où deux sommets sont reliés si et seulement si leur différence est un résidu quadratique. Ces graphes doivent leur nom au mathématicien anglais Raymond Paley. Les graphes de Paley forment une famille infinie de graphes de conférence, ce qui permet d'obtenir une famille infinie de matrices de conférences symétriques.
Graphe fortement régulierEn théorie des graphes, qui est un domaine des mathématiques, un graphe fortement régulier est un type de graphe régulier. Soit G = (V,E) un graphe régulier ayant v sommets et degré k. On dit que G est fortement régulier s'il existe deux entiers λ et μ tels que Toute paire de sommets adjacents a exactement λ voisins communs. Toute paire de sommets non-adjacents a exactement μ voisins communs. Un graphe avec ces propriétés est appelé un graphe fortement régulier de type (v,k,λ,μ).
Voisinage (théorie des graphes)En théorie des graphes on dit que deux sommets d'un graphe non-orienté sont voisins ou adjacents s'ils sont reliés par une arête. Le voisinage d'un sommet peut désigner l'ensemble de ses sommets voisins ou bien un sous-graphe associé, par exemple le sous-graphe induit. Dans un graphe orienté, on emploie généralement le terme de prédécesseur ou de successeur. Dans un graphe non orienté , le voisinage d'un sommet , souvent noté (N pour neighbourhood) peut désigner plusieurs choses : L'ensemble des sommets voisins : Les sous-graphe de induit par les sommets précédents, avec ou sans selon les versions.
Line graphEn théorie des graphes, le line graph L(G) d'un graphe non orienté G, est un graphe qui représente la relation d'adjacence entre les arêtes de G. Le nom line graph vient d'un article de Harary et Norman publié en 1960. La même construction avait cependant déjà été utilisée par Whitney en 1932 et Krausz en 1943. Il est également appelé graphe adjoint. Un des premiers et des plus importants théorèmes sur les line graphs est énoncé par Hassler Whitney en 1932, qui prouve qu'en dehors d'un unique cas exceptionnel, la structure de G peut être entièrement retrouvée à partir de L(G) dans le cas des graphes connexes.
Graphe parfaitEn théorie des graphes, le graphe parfait est une notion introduite par Claude Berge en 1960. Il s'agit d'un graphe pour lequel le nombre chromatique de chaque sous-graphe induit et la taille de la plus grande clique dudit sous-graphe induit sont égaux. Un graphe est 1-parfait si son nombre chromatique (noté ) est égal à la taille de sa plus grande clique (notée ) : . Dans ce cas, est parfait si et seulement si tous les sous graphes de sont 1-parfait.
