Alpha-critical Graphs

An alpha-critical graph is one, like an odd cycle or complete graph, where the removal of any edge increases the independence number. I computed all of the connected ones up to n=9 for kicks. They are kind of fun, so I’ll record them here.

alpha_critical6

Here is a list of the graph6 strings for the non-trivial (non-odd-cycle and non-complete) alpha-critical graphs on 6 to 9 vertices. (The ones with less than 6 vertices are trivial.)

n=6

1. E~~w

alpha_critical7

n=7

1. F~[KG

2. FzEKW

3. Fn[kG

alpha_critical8a

 

n=8

1. GbL|TS

2. G~?mvc

3. GbMmvG

4. Gb?kTG

5. GzD{Vg

6. Gb?kR_

7. GbqlZ_

8. GbilZ_

9. GbDKPG

n=9

alpha_critical9

1. HzCGKFo

2. H~|wKF{

3. Hj\x{F{

4. HnLk]My

5. HhcWKF_

6. HhKWKF_

7. HhCW[F_

8. HxCw}V`

9. HhcGKf_

10. HhKGKf_

11. Hh[gMEO

12. HhdGKE[

13. HhcWKE[

14. HhdGKFK

15. Hn[gGE@

16. Hn^zxU@

17. HlDKhEH

18. HhfJGE@

19. HnKmH]N

20. HnvzhEH

21. HhdJGM@

22. Hj~KHeF

23. HhdGHeB

24. HhXg[EO

25. HhGG]ES

26. H~Gg]f{

27. H~?g]vs

28. H~@w[Vs

29. Hn_k[^o

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s