Ogled vira Biggs-Smithov graf

{{infopolje graf
 | name = Biggs-Smithov graf
 | image = [[Slika:Biggs-Smith graph.svg|250px]]
 | image_caption = Biggs-Smithov graf
 | namesake = [[Norman Linstead Biggs]] <br /> [[Derek Howard Smith]] 
 | vertices = 102
 | edges = 153
 | automorphisms= 2448 ([[projektivna linearna grupa|PSL]](2,17))
 | girth = 9
 | radius = 7
 | diameter = 7
 | chromatic_number = 3
 | chromatic_index = 3
 | properties = [[simetrični graf|simetričen]]<br />[[po razdaljah regularni graf|razdaljno-regularen]]<br />[[kubični graf|kubičen]]<br>[[Hamiltonova pot|Hamiltonov]]
| genus = 
| notation = <math>F_{102}A\!\, </math>
}}

'''Biggs-Smithov graf''' je v [[teorija grafov|teoriji grafov]] [[neusmerjeni graf|neusmerjeni]] [[regularni graf|regularni graf stopnje 3]] s [[102 (število)|102]] [[točka (teorija grafov)|točkama]] in [[153 (število)|153]] [[graf (matematika)|povezavami]]. Imenuje se po angleških matematikih [[Norman Linstead Biggs|Normanu Linsteadu Biggsu]] in [[Derek Howard Smith|Dereku Howardu Smithu]].

Njegovo [[kromatično število]] je 3, [[kromatični indeks]] 3, [[razdalja (teorija grafov)|premer]] 7, polmer 7 in [[obseg (teorija grafov)|notranji obseg]] 9. Biggs-Smithov graf je tudi 3-[[po točkah k-povezani graf|točkovno-povezan]] in [[po povezavah k-povezani graf|3-povezavno-povezan]].

Znani so vsi [[kubični graf|kubični]] [[po razdaljah regularni graf|razdaljno-regularni grafi]].<ref>{{sktxt|Brouwer|Cohen|Neumaier|1989}}.</ref> Biggs-Smithov graf je dvanajsti od trinajstih takšnih grafov.

== Algebrske značilnosti ==

Grupa [[avtomorfizem grafa|avtomorfizmov]] Biggs-Smithovega grafa je [[grupa]] reda 2448, [[izomorfizem|izomorfna]] [[projektivna linearna grupa|projektivni linearni grupi]] PSL(2,17). Biggs-Smithov graf je [[po točkah prehodni grah|točkovno]] in [[po povezavah prehodni graf|povezavno-prehoden]], ter zato [[simetrični graf|simetričen]]. Ima avtomorfizme za vsak par točk in povezav. Po [[Fosterjev popis|Fosterjevem popisu]], kjer je označen kot F102A, je edini kubični simetrični graf na 102 točkah.<ref>{{sktxt|Conder|Dobcsányi|2002}}.</ref>

Biggs-Smithov graf je enolično določen s svojim [[spekter grafa|spektrom]], množico [[lastna vrednost|lastnih vrednosti]] svoje [[matrika sosednosti|matrike sosednosti]].<ref>{{sktxt|Van Dam|Haemers|2003}}.</ref>

[[karakteristični polinom (linearna algebra)|Karakteristični polinom]] Biggs-Smithovega grafa je:

: <math>(x-3) (x-2)^{18} x^{17} (x^{2}-x-4)^{9} (x^{3}+3 x^{2}-3)^{16} \!\, . </math>

== Upodobitve ==

<gallery>
Biggs-Smith graph 3COL.svg|[[Kromatično število]] Biggs-Smithovega grafa je 3.
Biggs-Smith graph 3color edge.svg|[[Kromatični indeks]] Biggs-Smithovega grafa je 3.
BiggsSmith.svg|Alternativna upodobitev Biggs-Smithovega grafa.
Biggs-Smith graph - circle-based drawing.jpg|Dekompozicija Biggs-Smithovega grafa v 6 množic z velikostjo 17.
</gallery>

== Sklici ==

{{sklici|3}}

== Viri ==

{{refbegin|2}}
* {{citat|last1= Biggs|first1= Norman Linstead|authorlink1= Norman Linstead Biggs|last2= Smith|first2= Derek Howard|authorlink2= Derek Howard Smith|title= On trivalent graphs|journal= [[Bulletin of the London Mathematical Society]]|date= 1971|volume= 3|issue= |pages= 155–158}}
* {{citat|last1= Brouwer|first1= Andries Evert|authorlink1= Andries Evert Brouwer|last2= Cohen|first2= A. M.|last3= Neumaier|first3= A.|title= Distance-Regular Graphs|publisher= Springer-Verlag|location= New York|date= 1989}}
* {{citat|last1= Conder|first1= Marston|authorlink1= Marston Conder|last2= Dobcsányi|first2= P.|title= Trivalent Symmetric Graphs Up to 768 Vertices|journal= [[Journal of Combinatorial Mathematics and Combinatorial Computing|J. Combin. Math. Combin. Comput.]]|date= 2002|volume= 40|issue= |pages= 41–63}}
* {{citat|last1= Van Dam|first1= E. R.|last2= Haemers|first2= W. H.|title= Spectral Characterizations of Some Distance-Regular Graphs|journal= [[Journal of Algebraic Combinatorics|J. Algebraic Combin.]]|date= 2003|volume= 15|issue= |pages= 189–202}}
{{refend}}

== Zunanje povezave ==

{{kategorija v Zbirki|Biggs-Smith graph}}
* {{MathWorld|id=Biggs-SmithGraph|title=Biggs-Smith Graph}}

{{math-stub}}

[[Kategorija:Posamezni grafi]]
[[Kategorija:Regularni grafi]]