Skip to main content
MathOverflow

Return to Answer

deleted 1 characters in body
Source Link
Hsien-Chih Chang 張顯之
Hsien-Chih Chang 張顯之
  • 1.3k
  • 2
  • 12
  • 21

This is the Moore graph, which is a regular graph of degree $d$ with diameter $k$, with maximum possible nodes. A calculation shows that the number of nodes $n$ is at leastmost

$$ 1+d \sum_{i=0}^{k-1} (d-1)^i $$

and as you mentioned it can be shown by spectral techniques that the only possible values for $d$ are

$$ d = 2,3,7,57. $$

Example for $d=7$ is the Hoffman–Singleton graph, but for the case $d=57$ it is still open. See Theorem 8.1.5 in the book "Spectra of graphs" by Brouwer and Haemers for reference.

This is the Moore graph, which is a regular graph of degree $d$ with diameter $k$, with maximum possible nodes. A calculation shows that the number of nodes $n$ is at least

$$ 1+d \sum_{i=0}^{k-1} (d-1)^i $$

and as you mentioned it can be shown by spectral techniques that the only possible values for $d$ are

$$ d = 2,3,7,57. $$

Example for $d=7$ is the Hoffman–Singleton graph, but for the case $d=57$ it is still open. See Theorem 8.1.5 in the book "Spectra of graphs" by Brouwer and Haemers for reference.

This is the Moore graph, which is a regular graph of degree $d$ with diameter $k$, with maximum possible nodes. A calculation shows that the number of nodes $n$ is at most

$$ 1+d \sum_{i=0}^{k-1} (d-1)^i $$

and as you mentioned it can be shown by spectral techniques that the only possible values for $d$ are

$$ d = 2,3,7,57. $$

Example for $d=7$ is the Hoffman–Singleton graph, but for the case $d=57$ it is still open. See Theorem 8.1.5 in the book "Spectra of graphs" by Brouwer and Haemers for reference.

deleted 14 characters in body
Source Link
Hsien-Chih Chang 張顯之
Hsien-Chih Chang 張顯之
  • 1.3k
  • 2
  • 12
  • 21

This is the Moore graph, which is a regular graph of degree $d$ with diameter $k$, with maximum possible nodes. A calculation shows that the number of nodes $n$ is at least

$$ 1+d \sum_{i=0}^{k-1} (d-1)^i $$

and as you mentioned it can be shown by spectral techniques that the only possible values for $d$ are

$$ d = 2,3,7,57. $$

Example for $d=7$ is the Hoffman–Singleton graphHoffman–Singleton graph, but for the case $d=57$ it is still open. See Theorem 8.1.5 in the book "Spectra of graphs" by Brouwer and Haemers for reference.

This is the Moore graph, which is a regular graph of degree $d$ with diameter $k$, with maximum possible nodes. A calculation shows that the number of nodes $n$ is at least

$$ 1+d \sum_{i=0}^{k-1} (d-1)^i $$

and as you mentioned it can be shown by spectral techniques that the only possible values for $d$ are

$$ d = 2,3,7,57. $$

Example for $d=7$ is the Hoffman–Singleton graph, but for the case $d=57$ it is still open. See Theorem 8.1.5 in the book "Spectra of graphs" by Brouwer and Haemers for reference.

This is the Moore graph, which is a regular graph of degree $d$ with diameter $k$, with maximum possible nodes. A calculation shows that the number of nodes $n$ is at least

$$ 1+d \sum_{i=0}^{k-1} (d-1)^i $$

and as you mentioned it can be shown by spectral techniques that the only possible values for $d$ are

$$ d = 2,3,7,57. $$

Example for $d=7$ is the Hoffman–Singleton graph, but for the case $d=57$ it is still open. See Theorem 8.1.5 in the book "Spectra of graphs" by Brouwer and Haemers for reference.

Source Link
Hsien-Chih Chang 張顯之
Hsien-Chih Chang 張顯之
  • 1.3k
  • 2
  • 12
  • 21

This is the Moore graph, which is a regular graph of degree $d$ with diameter $k$, with maximum possible nodes. A calculation shows that the number of nodes $n$ is at least

$$ 1+d \sum_{i=0}^{k-1} (d-1)^i $$

and as you mentioned it can be shown by spectral techniques that the only possible values for $d$ are

$$ d = 2,3,7,57. $$

Example for $d=7$ is the Hoffman–Singleton graph, but for the case $d=57$ it is still open. See Theorem 8.1.5 in the book "Spectra of graphs" by Brouwer and Haemers for reference.