Graphe distance-régulier

In the mathematical field of graph theory, a distance-regular graph is a regular graph such that for any two vertices v and w, the number of vertices at distance j from v and at distance k from w depends only upon j, k, and the distance between v and w. Some authors exclude the complete graphs and disconnected graphs from this definition. Every distance-transitive graph is distance-regular. Indeed, distance-regular graphs were introduced as a combinatorial generalization of distance-transitive graphs, having the numerical regularity properties of the latter without necessarily having a large automorphism group. It turns out that a graph of diameter is distance-regular if and only if there is an array of integers such that for all , gives the number of neighbours of at distance from and gives the number of neighbours of at distance from for any pair of vertices and at distance on . The array of integers characterizing a distance-regular graph is known as its intersection array. A pair of connected distance-regular graphs are cospectral if and only if they have the same intersection array. A distance-regular graph is disconnected if and only if it is a disjoint union of cospectral distance-regular graphs. Suppose is a connected distance-regular graph of valency with intersection array . For all : let denote the -regular graph with adjacency matrix formed by relating pairs of vertices on at distance , and let denote the number of neighbours of at distance from for any pair of vertices and at distance on . for all . and . for any eigenvalue multiplicity of , unless is a complete multipartite graph. for any eigenvalue multiplicity of , unless is a cycle graph or a complete multipartite graph. if is a simple eigenvalue of . has distinct eigenvalues. If is strongly regular, then and . Some first examples of distance-regular graphs include: The complete graphs. The cycles graphs. The odd graphs. The Moore graphs. The collinearity graph of a regular near polygon. The Wells graph and the Sylvester graph.

À 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.

Publications associées (30)

Personnes associées (7)

Unités associées (2)

Concepts associés (15)

Cours associés (1)

Séances de cours associées (20)

MATH-335: Coxeter groups

Study groups generated by reflections

ON THE INDEPENDENCE NUMBER OF INTERSECTION GRAPHS OF AXIS-PARALLEL SEGMENTS

Jana Tabea Cslovjecsek

We prove that for any triangle-free intersection graph of n axis-parallel line segments in the plane, the independence number alpha of this graph is at least alpha n/4+ohm(root n). We complement this with a construction of a graph in this class satisfying ...

Ottawa2023

An integer linear program is a problem of the form max{c^T x : Ax=b, x >= 0, x integer}, where A is in Z^(n x m), b in Z^m, and c in Z^n.Solving an integer linear program is NP-hard in general, but there are several assumptions for which it becomes fixed p ...

EPFL2023

, ,

The metric dimension (MD) of a graph is a combinatorial notion capturing the minimum number of landmark nodes needed to distinguish every pair of nodes in the graph based on graph distance. We study how much the MD can increase if we add a single edge to t ...

2022

Automorphisme de graphe

vignette|On peut définir deux automorphismes sur le graphe maison : l'identité et la permutation qui échange les deux « murs » de la « maison ». En mathématiques et en particulier en théorie des graphes, un automorphisme de graphe est une bijection de l'ensemble des sommets vers lui-même qui préserve l'ensemble des arêtes. On peut voir l'automorphisme de graphes comme un isomorphisme de graphes du graphe dans lui-même. On peut en général s'arranger pour mettre en évidence visuellement les automorphismes de graphes sous forme de symétries dans le tracé du graphe.

Graphe de Coxeter

En théorie des graphes, le graphe de Coxeter est un graphe cubique symétrique à 28 sommets et 42 arêtes. Il est nommé en l'honneur de H.S.M. Coxeter qui l'appelait « My graph ». Le diamètre du graphe de Coxeter, l'excentricité maximale de ses sommets, est 4, son rayon, l'excentricité minimale de ses sommets, est 4 et sa maille, la longueur de son plus court cycle, est 7. Il s'agit d'un graphe 3-sommet-connexe et d'un graphe 3-arête-connexe, c'est-à-dire qu'il est connexe et que pour le rendre déconnecté il faut le priver au minimum de 3 sommets ou de 3 arêtes.

Graphe distance-transitif

En théorie des graphes, un graphe non-orienté est distance-transitif si pour tous sommets u, v, x, y tels que u et v d'une part et x et y d'autre part sont à même distance, il existe un automorphisme de graphe envoyant u sur x et v sur y. Autrement dit, un graphe est distance-transitif si son groupe d'automorphisme agit transitivement sur chacun des ensembles de paires de sommets à même distance. Tout graphe distance-transitif est distance-régulier.

Valeurs propres et séquences MATH-467: Probabilistic methods in combinatorics

Discute de la recherche de graphes d-réguliers avec des propriétés de valeur propre spécifiques et de l'existence de séquences de Ramasugan pour les nombres premiers d-opt.

Graphiques positifs de Coxeter MATH-335: Coxeter groups

Explore la classification des graphiques de Coxeter positifs et définis à l'aide de calculs et d'épreuves détaillés.

Groupes de Coxeter : classification et régions fondamentales MATH-335: Coxeter groups

Explore la classification des groupes de Coxeter, les ordres de rotation, les régions fondamentales et l'équivalence géométrique.