Graphe completEn théorie des graphes, un graphe complet est un graphe simple dont tous les sommets sont adjacents deux à deux, c'est-à-dire que tout couple de sommets disjoints est relié par une arête. Si le graphe est orienté, on dit qu'il est complet si chaque paire de sommets est reliée par exactement deux arcs (un dans chaque sens). Un graphe complet est un graphe dont tous les sommets sont adjacents. À isomorphisme près, il n'existe qu'un seul graphe complet non orienté d'ordre n, que l'on note .
Logique des graphesDans les domaines mathématiques de la théorie des graphes et de la théorie des modèles finis, le logique des graphes traite de la spécification formelle de propriétés de graphe en utilisant des proposition de la logique mathématique. Il existe plusieurs variantes suivant les types d'opérations logiques qui peuvent être utilisées dans ces propositions. La logique du premier ordre des graphes concerne les propositions dans lesquelles les variables et les prédicats concernent les sommets et les arêtes individuels d'un graphe, tandis que la logique monadique de graphe du second ordre permet une quantification sur des ensembles de sommets ou d'arêtes.
Graphe à distance héréditairevignette| Exemple d'un graphe à distance héréditaire. En théorie des graphes, un graphe à distance héréditaire (aussi appelé graphe complètement séparable) est un graphe dans lequel les distances entre sommets dans tout sous-graphe induit connexe sont les mêmes que celles du graphe tout entier ; autrement dit, tout sous-graphe induit hérite les distances du graphe entier. Les graphes à distance héréditaire ont été nommés et étudiés pour la première fois par Howorka en 1977, alors qu'une classe équivalente de graphes a déjà été considérée en 1970 par Olaru et Sachs qui ont montré que ce sont des graphes parfaits.
Klaus WagnerKlaus Wagner (né le et mort le ) est un mathématicien allemand, connu dans son pays pour son rôle de pionnier de la théorie des graphes. Wagner étudia la topologie à l'université de Cologne sous la supervision de , lui-même ancien étudiant d'Issai Schur. Il reçut son doctorat en 1937 et enseigna à Cologne pendant de nombreuses années. En 1970, il choisit ce qui est aujourd'hui l'université de Duisbourg et Essen et il y resta jusqu'à sa retraite en 1978. Une festschrift fut publiée en son honneur en 1990.
Graphe sans triangleEn théorie des graphes, un graphe sans triangle est un graphe qui ne possède pas de triplet d'arêtes formant un triangle. Le théorème de Mantel, cas particulier du théorème de Turán, est : La famille des graphes sans triangle, contient notamment les graphes acycliques et est contenue dans les graphes sans diamant. Les graphes sans triangle peuvent être reconnus en temps , où est le nombre d'arêtes. De façon plus générale, on peut reconnaître les graphes n'ayant pas de cycles d'une certaine longueur (fixé dans l'algorithme), en temps (avec le nombre de sommets) ou en temps .
Apollonian networkIn combinatorial mathematics, an Apollonian network is an undirected graph formed by a process of recursively subdividing a triangle into three smaller triangles. Apollonian networks may equivalently be defined as the planar 3-trees, the maximal planar chordal graphs, the uniquely 4-colorable planar graphs, and the graphs of stacked polytopes. They are named after Apollonius of Perga, who studied a related circle-packing construction.
