Jump to content

Talk:Regular graph

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

Untitled

[edit]

"When the graph is regular with degree k, the graph will be connected if and only if k has algebraic (and geometric) dimension one."

What does this mean?

I'm sorry for the very late reply. The algebraic dimension is the number of times the eigenvalue is a zero of the characteristic polynomial, the geometric dimension is the dimension of the eigenspace. As the adjacency matrix is symmetric, these two dimensions are the same.Evilbu (talk) 13:05, 9 August 2009 (UTC)[reply]

Algebraic properties and other properties

[edit]

I'd much rather see having a section about properites of regular graphs and merging general properties and algebraic properties together. Stdazi (talk) 19:33, 2 June 2012 (UTC)[reply]

Num of edges

[edit]

Is it n*k/2 (should be) - it would be a good addition The ubik (talk) 22:35, 18 September 2012 (UTC)[reply]

Existence

[edit]

Shouldn't the existence formula be n>=k-1 (and nk is even)? For n=1, k can = 2 (loop to itself), and loops are allowed in a regular graph. For n=2, k can = 3 (loop itself & to the other node)? Maybe i'm missing something here... Lilfolr (talk) 14:24, 15 June 2016 (UTC) lilfolr[reply]

Nomenclature

[edit]

While I was a graduate student in mathematics, I found a book of mathematical recreations, in French, in the University of Buffalo's math library. It had a chapter on graphs, and it said that a graph is "cubique" if each of its vertices has exactly 3 edges. In modern terminology we would say that a cubic graph is one that is 3-regular.

The book also said that a 4-regular graph is said to be "quadrillé" (quadrille), and it gave a term for a 5-regular graph that I have forgotten. Has anyone else encountered these terms? Sicherman (talk) 15:19, 21 April 2018 (UTC)[reply]

Generation

[edit]

This references a paper from 1999. Is this still the state of the art? Do we know anything about the asymptotic complexity of this problem? I didn't write "efficient" because they don't give any complexity results. Also, the numbers in that paper are a bit underwhelming. Do we have any more recent figures on this? Sschuldenzucker (talk) 18:14, 24 June 2019 (UTC)[reply]