Graph powerIn graph theory, a branch of mathematics, the kth power G^k of an undirected graph G is another graph that has the same set of vertices, but in which two vertices are adjacent when their distance in G is at most k. Powers of graphs are referred to using terminology similar to that of exponentiation of numbers: G^2 is called the square of G, G^3 is called the cube of G, etc. Graph powers should be distinguished from the products of a graph with itself, which (unlike powers) generally have many more vertices than the original graph.
Lovász conjectureIn graph theory, the Lovász conjecture (1969) is a classical problem on Hamiltonian paths in graphs. It says: Every finite connected vertex-transitive graph contains a Hamiltonian path. Originally László Lovász stated the problem in the opposite way, but this version became standard. In 1996, László Babai published a conjecture sharply contradicting this conjecture, but both conjectures remain widely open. It is not even known if a single counterexample would necessarily lead to a series of counterexamples.
Graphe de Halinthumb|Un graphe de Halin. En théorie des graphes, une branche des mathématiques, un graphe de Halin est un graphe planaire construit à partir d'un arbre en reliant toutes ses feuilles dans un cycle qui fait le tour de l'arbre de telle façon que l'arbre reste planaire. On exige de plus que l'arbre comporte au moins quatre sommets et ne comporte pas de sommets de degré 2. Les graphes de Halin graphs sont nommés d'après le mathématicien allemand Rudolf Halin qui les a étudiés en 1971, mais les graphes de Halin cubiques avaient déjà été étudiés plus d'un siècle auparavant par Thomas Kirkman.
Graphe hypohamiltonienEn théorie des graphes, un graphe est hypohamiltonien s'il n'a pas de cycle hamiltonien mais que la suppression de n'importe quel sommet du graphe suffit à le rendre hamiltonien. Les graphes hypohamiltoniens furent étudiés pour la première fois par Sousselier en 1963 dans Problèmes plaisants et délectables. Sous forme d'une petite énigme la notion est introduite. L'énoncé demande de trouver un tel graphe d'ordre 10 (le graphe de Petersen) et de prouver que cet ordre est minimal, c'est-à-dire qu'il n'existe pas de graphe hypohamiltonien à moins de 10 sommets.
Snake-in-the-boxThe snake-in-the-box problem in graph theory and computer science deals with finding a certain kind of path along the edges of a hypercube. This path starts at one corner and travels along the edges to as many corners as it can reach. After it gets to a new corner, the previous corner and all of its neighbors must be marked as unusable. The path should never travel to a corner which has been marked unusable.
Graphe aléatoirevignette|Graphe orienté aléatoire avec 20 nœuds et une probabilité de présence d'arête égale à 0,1. En mathématiques, un graphe aléatoire est un graphe généré par un processus aléatoire. Le premier modèle de graphes aléatoires a été popularisé par Paul Erdős et Alfréd Rényi dans une série d'articles publiés entre 1959 et 1968. Il y a deux modèles d'Erdős et Rényi, formellement différents, mais étroitement liés : le graphe aléatoire binomial et le graphe aléatoire uniforme.
Théorème de Fleischnervignette|upright=1.3| Un graphe biconnexe, son carré et un cycle hamiltonien dans le carré. En théorie des graphes, le théorème de Fleischner donne une condition suffisante pour qu'un graphe contienne un cycle hamiltonien. Il dit que le d'un graphe biconnexe est un graphe hamiltonien. Le théorème porte le nom de Herbert Fleischner, qui en a publié la preuve en 1974. Un graphe non orienté G est hamiltonien s'il contient un cycle qui passe par chacun de ses sommets exactement une fois.
Cube-connected cyclesIn graph theory, the cube-connected cycles is an undirected cubic graph, formed by replacing each vertex of a hypercube graph by a cycle. It was introduced by for use as a network topology in parallel computing. The cube-connected cycles of order n (denoted CCCn) can be defined as a graph formed from a set of n2n nodes, indexed by pairs of numbers (x, y) where 0 ≤ x < 2n and 0 ≤ y < n. Each such node is connected to three neighbors: (x, (y + 1) mod n), (x, (y − 1) mod n), and (x ⊕ 2y, y), where "⊕" denotes the bitwise exclusive or operation on binary numbers.
Graphe de TutteLe graphe de Tutte est, en théorie des graphes, un graphe 3-régulier possédant 46 sommets et 69 arêtes. Le graphe de Tutte est découvert par le mathématicien William Tutte en 1946. C'est le premier contre-exemple connu à la conjecture de Tait sur les graphes hamiltoniens, c'est-à-dire que c'est un graphe planaire non-hamiltonien étant 3-sommet-connexe. Le graphe de Tutte est suivi de la construction de plusieurs autres contre-exemples à cette conjecture.
Graphe de HeawoodEn théorie des graphes, le graphe de Heawood est un graphe cubique symétrique possédant 14 sommets et 21 arêtes. Il doit son nom à Percy John Heawood, un mathématicien britannique né en 1861 et mort en 1955. Le graphe de Heawood est une (3,6)-cage, c'est-à-dire un graphe minimal en nombres de sommets ayant une maille de 6 et étant cubique. En fait, il s'agit de l'unique (3,6)-cage et sa taille coïncide avec la borne de Moore, une borne inférieure sur le nombre de sommets que peut avoir une cage.
