Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
List of graphs
Summary
This partial list of graphs contains definitions of graphs and graph families. For collected definitions of graph theory terms that do not refer to individual graph types, such as vertex and path, see Glossary of graph theory. For links to existing articles about particular kinds of graphs, see . Some of the finite structures considered in graph theory have names, sometimes inspired by the graph's topology, and sometimes after their discoverer. A famous example is the Petersen graph, a concrete graph on 10 vertices that appears as a minimal example or counterexample in many different contexts.
File:Balaban 10-cage alternative drawing.svg|[[Balaban 10-cage]]
File:Balaban 11-cage.svg|[[Balaban 11-cage]]
File:Bidiakis cube.svg|[[Bidiakis cube]]
File:Brinkmann graph LS.svg|[[Brinkmann graph]]
File:Bull graph.circo.svg|[[Bull graph]]
File:Butterfly graph.svg|[[Butterfly graph]]
File:Chvatal graph.draw.svg|[[Chvátal graph]]
File:Diamond graph.svg|[[Diamond graph]]
File:Dürer graph.svg|[[Dürer graph]]
File:Ellingham-Horton 54-graph.svg|[[Ellingham–Horton 54-graph]]
File:Ellingham-Horton 78-graph.svg|[[Ellingham–Horton 78-graph]]
File:Errera graph.svg|[[Errera graph]]
File:Franklin graph.svg|[[Franklin graph]]
File:Frucht planar Lombardi.svg|[[Frucht graph]]
File:Goldner-Harary graph.svg|[[Goldner–Harary graph]]
File:GolombGraph.svg|[[Golomb graph]]
File:Groetzsch-graph.svg|[[Grötzsch graph]]
File:Harries graph alternative_drawing.svg|[[Harries graph]]
File:Harries-wong graph.svg|[[Harries–Wong graph]]
File:Herschel graph no col.svg|[[Herschel graph]]
File:Hoffman graph.svg|[[Hoffman graph]]
File:Holt graph.svg|[[Holt graph]]
File:Horton graph.svg|[[Horton graph]]
File:Kittell graph.svg|[[Kittell graph]]
File:Markström-Graph.svg|[[Erdős–Gyárfás conjecture|Markström graph]]
File:McGee graph.svg|[[McGee graph]]
File:Meredith graph.svg|[[Meredith graph]]
File:Moser spindle.svg |[[Moser spindle]]
File:Sousselier graph.svg|[[Sousselier graph]]
File:Poussin graph planar.svg|[[Poussin graph]]
File:Robertson graph.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
Related courses (22)
MATH-448: Statistical analysis of network data
A first course in statistical network analysis and applications.
MATH-260(a): Discrete mathematics
Study of structures and concepts that do not require the notion of continuity. Graph theory, or study of general countable sets are some of the areas that are covered by discrete mathematics. Emphasis
MATH-602: Inference on graphs
The class covers topics related to statistical inference and algorithms on graphs: basic random graphs concepts, thresholds, subgraph containment (planted clique), connectivity, broadcasting on trees,
Related lectures (90)
Eigenvalues and Sequences
Discusses finding d-regular graphs with specific eigenvalue properties and the existence of Ramasugan sequences for d-opt prime numbers.
Temporal Summation Analysis
Covers the analysis of temporal summations in bio mechanics.
Social Cognition
Delves into social cognition, collaborative learning effectiveness, group consensus, and the role of technology in enhancing interactions.
Related publications (146)
Non-planarity of Markoff graphs mod p
We prove the non-planarity of a family of 3-regular graphs constructed from the solutions to the Markoff equation x2 + y2 + z2 = xyz modulo prime numbers greater than 7. The proof uses Euler characteristic and an enumeration of the short cycles in these gr ...
Berlin2024High-Throughput and Flexible Belief Propagation List Decoder for Polar Codes
Andreas Peter Burg, Alexios Konstantinos Balatsoukas Stimming, Andreas Toftegaard Kristensen, Yifei Shen, Yuqing Ren, Leyu Zhang, Chuan Zhang
Due to its high parallelism, belief propagation (BP)decoding is amenable to high-throughput applications and thusrepresents a promising solution for the ultra-high peak datarate required by future communication systems. To bridge theperformance gap compare ...
Ieee-Inst Electrical Electronics Engineers Inc2024A Note on Lenses in Arrangements of Pairwise Intersecting Circles in the Plane
Let F be a family of n pairwise intersecting circles in the plane. We show that the number of lenses, that is convex digons, in the arrangement induced by F is at most 2n - 2. This bound is tight. Furthermore, if no two circles in F touch, then the geometr ...
Electronic Journal Of Combinatorics2024Related people (35)
Related units (4)
Related concepts (10)
Forbidden graph characterization
In graph theory, a branch of mathematics, many important families of graphs can be described by a finite set of individual graphs that do not belong to the family and further exclude all graphs from the family which contain any of these forbidden graphs as (induced) subgraph or minor. A prototypical example of this phenomenon is Kuratowski's theorem, which states that a graph is planar (can be drawn without crossings in the plane) if and only if it does not contain either of two forbidden graphs, the complete graph K_5 and the complete bipartite graph K_3,3.
Hypercube graph
In graph theory, the hypercube graph Q_n is the graph formed from the vertices and edges of an n-dimensional hypercube. For instance, the cube graph Q_3 is the graph formed by the 8 vertices and 12 edges of a three-dimensional cube. Q_n has 2^n vertices, 2^n – 1n edges, and is a regular graph with n edges touching each vertex. The hypercube graph Q_n may also be constructed by creating a vertex for each subset of an n-element set, with two vertices adjacent when their subsets differ in a single element, or by creating a vertex for each n-digit binary number, with two vertices adjacent when their binary representations differ in a single digit.
Star (graph theory)
In graph theory, a star S_k is the complete bipartite graph K_1,k : a tree with one internal node and k leaves (but no internal nodes and k + 1 leaves when k ≤ 1). Alternatively, some authors define S_k to be the tree of order k with maximum diameter 2; in which case a star of k > 2 has k − 1 leaves. A star with 3 edges is called a claw. The star S_k is edge-graceful when k is even and not when k is odd. It is an edge-transitive matchstick graph, and has diameter 2 (when l > 1), girth ∞ (it has no cycles), chromatic index k, and chromatic number 2 (when k > 0).
Related MOOCs (1)
SES Swiss-Energyscope
La transition énergique suisse / Energiewende in der Schweiz