Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Concept
Graphe de Folkman
Résumé
In the mathematical field of graph theory, the Folkman graph is a 4-regular graph with 20 vertices and 40 edges. It is a regular bipartite graph with symmetries taking every edge to every other edge, but the two sides of its bipartition are not symmetric with each other, making it the smallest possible semi-symmetric graph. It is named after Jon Folkman, who constructed it for this property in 1967.
The Folkman graph can be constructed either using modular arithmetic or as the subdivided double of the five-vertex complete graph. Beyond the investigation of its symmetry, it has also been investigated as a counterexample for certain questions of graph embedding.
Semi-symmetric graphs are defined as regular graphs (that is, graphs in which all vertices touch equally many edges) in which each two edges are symmetric to each other, but some two vertices are not symmetric. Jon Folkman was inspired to define and research these graphs in a 1967 paper, after seeing an unpublished manuscript by E. Dauber and Frank Harary which gave examples of graphs meeting the symmetry condition but not the regularity condition. Folkman's original construction of this graph was a special case of a more general construction of semi-symmetric graphs using modular arithmetic, based on a prime number congruent to 1 mod 4. For each such prime, there is a number such that mod , and Folkman uses modular arithmetic to construct a semi-symmetric graph with vertices. The Folkman graph is the result of this construction for and .
Another construction for the Folkman graph begins with the complete graph on five vertices, . A new vertex is placed on each of the ten edges of , subdividing each edge into a two-edge path. Then, each of the five original vertices of is doubled, replacing it by two vertices with the same neighbors. The ten subdivision vertices form one side of the bipartition of the Folkman graph, and the ten vertices in twin pairs coming from the doubled vertices of form the other side of the bipartition.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.