Skip to main content
fixed typo
Source Link
Chris Godsil
  • 12.1k
  • 5
  • 37
  • 61

Not particularly. There is a paper by Codenotti, Gerace, Vigna "Hardness results and spectral techniques for combinatorial problems on circulant graphs" LinerLinear Algebra Appl. 285 (1998) 123-142 which shows that computing the chromatic number of a circulant graph is NP-hard. (The pdf is available on Codenotti's web page.) Being vertex transitive guarantees that a $k$-regular graph has vertex connectivity at at least $2(k+1)/3$ and that its edge connectivity is equal to $k$. Aside from this, it is not easy to identify useful consequences of vertex transitivity.

Not particularly. There is a paper by Codenotti, Gerace, Vigna "Hardness results and spectral techniques for combinatorial problems on circulant graphs" Liner Algebra Appl. 285 (1998) 123-142 which shows that computing the chromatic number of a circulant graph is NP-hard. (The pdf is available on Codenotti's web page.) Being vertex transitive guarantees that a $k$-regular graph has vertex connectivity at at least $2(k+1)/3$ and that its edge connectivity is equal to $k$. Aside from this, it is not easy to identify useful consequences of vertex transitivity.

Not particularly. There is a paper by Codenotti, Gerace, Vigna "Hardness results and spectral techniques for combinatorial problems on circulant graphs" Linear Algebra Appl. 285 (1998) 123-142 which shows that computing the chromatic number of a circulant graph is NP-hard. (The pdf is available on Codenotti's web page.) Being vertex transitive guarantees that a $k$-regular graph has vertex connectivity at at least $2(k+1)/3$ and that its edge connectivity is equal to $k$. Aside from this, it is not easy to identify useful consequences of vertex transitivity.

Source Link
Chris Godsil
  • 12.1k
  • 5
  • 37
  • 61

Not particularly. There is a paper by Codenotti, Gerace, Vigna "Hardness results and spectral techniques for combinatorial problems on circulant graphs" Liner Algebra Appl. 285 (1998) 123-142 which shows that computing the chromatic number of a circulant graph is NP-hard. (The pdf is available on Codenotti's web page.) Being vertex transitive guarantees that a $k$-regular graph has vertex connectivity at at least $2(k+1)/3$ and that its edge connectivity is equal to $k$. Aside from this, it is not easy to identify useful consequences of vertex transitivity.