To install click the Add extension button. That's it.

The source code for the WIKI 2 extension is being checked by specialists of the Mozilla Foundation, Google, and Apple. You could also do it yourself at any point in time.

4,5
Kelly Slayton
Congratulations on this excellent venture… what a great idea!
Alexander Grigorievskiy
I use WIKI 2 every day and almost forgot how the original Wikipedia looks like.
Live Statistics
English Articles
Improved in 24 Hours
Added in 24 Hours
What we do. Every page goes through several hundred of perfecting techniques; in live mode. Quite the same Wikipedia. Just better.
.
Leo
Newton
Brights
Milds

Distance-regular graph

From Wikipedia, the free encyclopedia

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.

YouTube Encyclopedic

  • 1/5
    Views:
    4 662
    95 645
    59 857
    33 121
    21 027
  • What are Regular Graphs? | Graph Theory
  • Graph Theory: 05. Connected and Regular Graphs
  • Graph Theory: 51. Eccentricity, Radius & Diameter
  • Graph Theory: 17. Distance Between Vertices and Connected Components
  • Graph Theory: 15.There Exists a 3-Regular Graph of All Even Order at least 4

Transcription

Intersection arrays

The intersection array of a distance-regular graph is the array in which is the diameter of the graph and for each , 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 . There is also the number that gives the number of neighbours of at distance from . The numbers are called the intersection numbers of the graph. They satisfy the equation where is the valency, i.e., the number of neighbours, of any vertex.

It turns out that a graph of diameter is distance regular if and only if it has an intersection array in the preceding sense.

Cospectral and disconnected distance-regular graphs

A pair of connected distance-regular graphs are cospectral if their adjacency matrices have the same spectrum. This is equivalent to their having the same intersection array.

A distance-regular graph is disconnected if and only if it is a disjoint union of cospectral distance-regular graphs.

Properties

Suppose is a connected distance-regular graph of valency with intersection array . For each let denote the number of vertices at distance from any given vertex and let denote the -regular graph with adjacency matrix formed by relating pairs of vertices on at distance .

Graph-theoretic properties

  • for all .
  • and .

Spectral properties

  • has distinct eigenvalues.
  • The only simple eigenvalue of is or both and if is bipartite.
  • 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 strongly regular, then and .

Examples

The degree 7 Klein graph and associated map embedded in an orientable surface of genus 3. This graph is distance regular with intersection array {7,4,1;1,2,7} and automorphism group PGL(2,7).

Some first examples of distance-regular graphs include:

Classification of distance-regular graphs

There are only finitely many distinct connected distance-regular graphs of any given valency .[1]

Similarly, there are only finitely many distinct connected distance-regular graphs with any given eigenvalue multiplicity [2] (with the exception of the complete multipartite graphs).

Cubic distance-regular graphs

The cubic distance-regular graphs have been completely classified.

The 13 distinct cubic distance-regular graphs are K4 (or Tetrahedral graph), K3,3, the Petersen graph, the Cubical graph, the Heawood graph, the Pappus graph, the Coxeter graph, the Tutte–Coxeter graph, the Dodecahedral graph, the Desargues graph, Tutte 12-cage, the Biggs–Smith graph, and the Foster graph.

References

  1. ^ Bang, S.; Dubickas, A.; Koolen, J. H.; Moulton, V. (2015-01-10). "There are only finitely many distance-regular graphs of fixed valency greater than two". Advances in Mathematics. 269 (Supplement C): 1–55. arXiv:0909.5253. doi:10.1016/j.aim.2014.09.025. S2CID 18869283.
  2. ^ Godsil, C. D. (1988-12-01). "Bounding the diameter of distance-regular graphs". Combinatorica. 8 (4): 333–343. doi:10.1007/BF02189090. ISSN 0209-9683. S2CID 206813795.

Further reading

This page was last edited on 7 December 2023, at 01:51
Basis of this page is in Wikipedia. Text is available under the CC BY-SA 3.0 Unported License. Non-text media are available under their specified licenses. Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc. WIKI 2 is an independent company and has no affiliation with Wikimedia Foundation.