Concept

Glossary of graph theory

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

Official source

https://en.wikipedia.org/wiki/Glossary_of_graph_theory

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 (32)

PHYS-467: Machine learning for physicists

Machine learning and data analysis are becoming increasingly central in sciences including physics. In this course, fundamental principles and methods of machine learning will be introduced and practised. ...

MATH-448: Statistical analysis of network data

A first course in statistical network analysis and applications. ...

CS-448: Sublinear algorithms

In this course we will define rigorous mathematical models for computing on large datasets, cover main algorithmic techniques that have been developed for sublinear (e.g. faster than linear time) data processing. We will also discuss limitations inherent t ...

Related lectures (32)

Belief Propagation

Explores Belief Propagation in graphical models, factor graphs, spin glass examples, Boltzmann distributions, and graph coloring properties.

Fixed Points in Graph Theory

Focuses on fixed points in graph theory and their implications in algorithms and analysis.

Linear Algebra: Diagonalization

Explores the diagonalization of matrices and the conditions for exact diagonalization, with examples demonstrating the process.

Related publications (7)

A Unified Framework for Modelling Modern Relational Network Data

This thesis concerns the nonparametric estimation of decorated graphons, symmetric measurable functions

W : [0,1]^2 \to \mathcal{P}(\mathcal{K})

that generalize classical graphon models beyond binary edges to networks carrying rich edge attributes such as weights and types. While decorated graphons were introduced as limit objects in graph theory, no estimation theory was available prior to this work. The thesis addresses this gap along three axes: rich edge attributes, temporal dynamics, and computationa

EPFL2026

Lower bounds for Ramsey numbers of bounded degree hypergraphs

We prove that, for all k≥3, and any integers Δ,n with n≥Δ, there exists a k-uniform hypergraph on n vertices with maximum degree at most Δ whose 4-color Ramsey number is at least twk(ckΔ)⋅n, for some constant ck>0, where twk denotes the tower function. For k≥4, this is tight up to the constant ck and for k=3 it is known to be tight up to a factor of log⁡Δ on top of the tower. Our bound extends a well-known result of Graham, Rödl and Ruciński for graphs and answers a question of Conlon, Fox and Sudakov from

Elsevier2026

Identifying Kronecker product factorizations

The Kronecker product is an invaluable tool for data-sparse representations of large networks and matrices with countless applications in machine learning, graph theory, and numerical linear algebra. In some instances, the sparsity pattern of large matrices may already hide a Kronecker product. Similarly, a large network, represented by its adjacency matrix, may sometimes be factorized as a Kronecker product of smaller adjacency matrices. In this article, we determine all possible Kronecker factorizations o

2026

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

Official source

https://en.wikipedia.org/wiki/Glossary_of_graph_theory

About this result

Ontological neighbourhood

Mathematics

Discrete mathematics: Graph theory

Related courses (32)

PHYS-467: Machine learning for physicists

MATH-448: Statistical analysis of network data

A first course in statistical network analysis and applications. ...

CS-448: Sublinear algorithms

Related lectures (32)

Belief Propagation

Explores Belief Propagation in graphical models, factor graphs, spin glass examples, Boltzmann distributions, and graph coloring properties.

Fixed Points in Graph Theory

Focuses on fixed points in graph theory and their implications in algorithms and analysis.

Linear Algebra: Diagonalization

Explores the diagonalization of matrices and the conditions for exact diagonalization, with examples demonstrating the process.

Related publications (7)

A Unified Framework for Modelling Modern Relational Network Data

This thesis concerns the nonparametric estimation of decorated graphons, symmetric measurable functions

W : [0,1]^2 \to \mathcal{P}(\mathcal{K})

EPFL2026

Lower bounds for Ramsey numbers of bounded degree hypergraphs

Elsevier2026

Identifying Kronecker product factorizations

2026

Related people (32)

Vittorio Erba

Teaching & PhD Courses Statistical physics of computation PHYS-512 The students understand tools from the statistical physics of disordered systems, and apply them to study computational and statistical problems in graph theory, discrete optimisation, inference and machine learning.

Giovanni De Micheli

Expertise Design technologies for integrated systems on silicon, such as synthesis, hw/sw codesign and low-power design, as well as systems on heterogeneous platforms including electrical and biological components. Scientific Director of EcoCloud Center at EPFL Directing activities towards creating sustainable computation including AI.Designing energy-savvy data centers and edge devices. More information Please read http://si2.epfl.ch/~demichel/ Giovanni De Micheli is a research scientist in electronics and

Volkan Cevher

Volkan Cevher received the B.Sc. (valedictorian) in electrical engineering from Bilkent University in Ankara, Turkey, in 1999 and the Ph.D. in electrical and computer engineering from the Georgia Institute of Technology in Atlanta, GA in 2005. He was a Research Scientist with the University of Maryland, College Park from 2006-2007 and also with Rice University in Houston, TX, from 2008-2009. Currently, he is an Associate Professor at the Swiss Federal Institute of Technology Lausanne and a Faculty Fellow in the Electrical and Computer Engineering Department at Rice University. His research interests include machine learning, signal processing theory, optimization theory and methods, and information theory. Dr. Cevher is an ELLIS fellow and was the recipient of the Google Faculty Research award in 2018, the IEEE Signal Processing Society Best Paper Award in 2016, a Best Paper Award at CAMSAP in 2015, a Best Paper Award at SPARS in 2009, and an ERC CG in 2016 as well as an ERC StG in 2011.

Pascal Frossard

Teaching & PhD PhD Students Yiming Qin, Alba Carballo Castro, Elisa Messori, Ke Wang, Sevda Ögüt, Tuna Alikasifoglu, William Cappelletti, Manuel Madeira, Mahdi Amiri, Ortal Yona Senouf, Vasiliki Rizou, Cem Bilaloglu, Abdellah Rahmani, Amel Abdelraheem, Jérémy Jean Philippe Baffou, Adam Hazimeh, Vincent Jung, Yike Zhao Past EPFL PhD Students Dan Jurca, Jean-Paul Wagner, Ivana Radulovic, Ivana Tosic, Effrosyni Kokiopoulou, Zafer Arican, Vijayaraghavan Thirumalai, Tamara Tosic, Eirina Bourtsoulatze, Elif Vur

Daniel Sage

Expertise PublicationsPublications Coordinates Biomedical Imaging GroupAddressEPFL STI-IMT-LIB, BM 4.135, Station 17, CH-1015 Lausanne, SwitzerlandTel.+41 21 693 51 89Fax.+41 21 693 68 10Emaildaniel.sage@epfl.chWeb pagehttp://bigwww.epfl.ch/sage/OfficeBM 4.135 Teaching & PhD Past EPFL PhD Students as codirector Daniel Andreas Schmitter, Anaïs Badoual, Laurène Donati Courses Bioimage informatics BIO-410 The course provides a comprehensive overview of methods, algorithms, and computer tools us

Sofia Charlotta Olhede

I am a professor of Statistics at EPFL. I did my PhD in Mathematics at Imperial College London, and graduated in 2003. I was an assistant professor (lecturer) at Imperial College London 2002-2006, and an associate professor (senior lecturer) 2006-2007. In 2007 I moved to University College London and became a full professor. I moved to EPFL in 2019, and in 2018 I became an Institute of Mathematical Statistics Fellow with citation “For seminal contributions to the theory and application of large and heteroge

Oliver Janzer

Teaching & PhD PhD Students Rik Sarkar Courses Algebraic methods in combinatorics MATH-526 In this course we study how algebraic methods can be used to solve problems in combinatorics. The main tools used are from linear algebra and from the theory of polynomials. Graph theory MATH-360 The course aims to introduce the basic concepts and results of modern Graph Theory. Awards European Prize in Combinatorics 2025 British Combinatorial Committee PhD Prize 2022 Smith-Knight

Anne-Florence Raphaëlle Bitbol

I was trained in physics, and always had a strong interest in biology. I am broadly interested in understanding biological phenomena in a quantitative way, through physical concepts and mathematical and computational tools. I investigate the relative impacts of optimization and historical contingency in biological evolution, both at the scale of protein sequences and at the scale of microbial populations.Here is my research group website.Curriculum vitae Here is my complete CV. Professional experience:Since

Alexandre Buttler

I am a honorary professor at Ecole Polytechnique Fédérale, Lausanne - EPFL. Up to 2019, I was a joint-professor between EPFL (Head of the laboratory of Ecological Systems - ECOS) and the Swiss Federal Research Institute WSL for Forest, Snow and Landscape (Head of the research group Pasture Woodlands and Wetlands) and head of the Site WSL-Lausanne. I was also professor at the laboratory of Chrono-Environnement (UMR CNRS 6249) of the University of Franche-Comté, Besançon (France). I am author or co-author of over 160 papers in international ISI cited peer-reviewed journals.

Etienne Michel François Bamas

Related units (32)

Transportation and Mobility Laboratory

Signal Processing Laboratory 4

SNAI - Administration

Related concepts (32)

Graph theory

In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of vertices (also called nodes or points) which are connected by edges (also called links or lines). A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges link two vertices asymmetrically. Graphs are one of the principal objects of study in discrete mathematics.

Cycle (graph theory)

In graph theory, a cycle in a graph is a non-empty trail in which only the first and last vertices are equal. A directed cycle in a directed graph is a non-empty directed trail in which only the first and last vertices are equal. A graph without cycles is called an acyclic graph. A directed graph without directed cycles is called a directed acyclic graph. A connected graph without cycles is called a tree. A circuit is a non-empty trail in which the first and last vertices are equal (closed trail).

Petersen graph

In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is named after Julius Petersen, who in 1898 constructed it to be the smallest bridgeless cubic graph with no three-edge-coloring. Although the graph is generally credited to Petersen, it had in fact first appeared 12 years earlier, in a paper by .

Related notebooks (1)

Powder X-Ray Diffraction Analysis: Exploring Crystal Structures.

XRay Diffraction[1]¶ The purpose of this notebook is to study the powder XRay diffraction spectra of some systems. When the crystal is hit with an XRay wave, the wave is diffracted only for specific case where the Bragg condition is satisfied for one of the lattice planes in the material. For single crystal diffraction, the condition is satisfied only for specific orientation of the crystal, such that the incident ray has the correct