Foster graph

Foster graph
The Foster graph
Named after	Ronald Martin Foster
Vertices	90
Edges	135
Radius	8
Diameter	8
Girth	10
Automorphisms	4320
Chromatic number	2
Chromatic index	3
Queue number	2
Properties	Cubic Bipartite Symmetric Hamiltonian Distance-transitive
Table of graphs and parameters

In the mathematical field of graph theory, the Foster graph is a bipartite 3-regular graph with 90 vertices and 135 edges.^[1]

The Foster graph is Hamiltonian and has chromatic number 2, chromatic index 3, radius 8, diameter 8 and girth 10. It is also a 3-vertex-connected and 3-edge-connected graph. It has queue number 2 and the upper bound on the book thickness is 4.^[2]

All the cubic distance-regular graphs are known.^[3] The Foster graph is one of the 13 such graphs. It is the unique distance-transitive graph with intersection array {3,2,2,2,2,1,1,1;1,1,1,1,2,2,2,3}.^[4] It can be constructed as the incidence graph of the partial linear space which is the unique triple cover with no 8-gons of the generalized quadrangle GQ(2,2). It is named after R. M. Foster, whose Foster census of cubic symmetric graphs included this graph.

The bipartite half of the Foster graph is a distance-regular graph and a locally linear graph. It is one of a finite number of such graphs with degree six.^[5]

Algebraic properties

The automorphism group of the Foster graph is a group of order 4320.^[6] It acts transitively on the vertices, on the edges and on the arcs of the graph. Therefore, the Foster graph is a symmetric graph. It has automorphisms that take any vertex to any other vertex and any edge to any other edge. According to the Foster census, the Foster graph, referenced as F90A, is the only cubic symmetric graph on 90 vertices.^[7]

The characteristic polynomial of the Foster graph is equal to $(x-3)(x-2)^{9}(x-1)^{18}x^{10}(x+1)^{18}(x+2)^{9}(x+3)(x^{2}-6)^{12}$ .

Gallery

Foster graph colored to highlight various cycles.
The chromatic number of the Foster graph is 2.
The chromatic index of the Foster graph is 3.

References

^ Weisstein, Eric W. "Foster Graph". MathWorld.
^ Wolz, Jessica; Engineering Linear Layouts with SAT. Master Thesis, University of Tübingen, 2018
^ Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. Distance-Regular Graphs. New York: Springer-Verlag, 1989.
^ Cubic distance-regular graphs, A. Brouwer.
^ Hiraki, Akira; Nomura, Kazumasa; Suzuki, Hiroshi (2000), "Distance-regular graphs of valency 6 and $a_{1}=1$ ", Journal of Algebraic Combinatorics, 11 (2): 101–134, doi:10.1023/A:1008776031839, MR 1761910
^ "G-12 Foster graph", Encyclopedia of Graphs, retrieved 2024-02-26
^ Conder, M. and Dobcsányi, P. "Trivalent Symmetric Graphs Up to 768 Vertices." J. Combin. Math. Combin. Comput. 40, 41-63, 2002.

Biggs, N. L.; Boshier, A. G.; Shawe-Taylor, J. (1986), "Cubic distance-regular graphs", Journal of the London Mathematical Society, 33 (3): 385–394, doi:10.1112/jlms/s2-33.3.385, MR 0850954.

Van Dam, Edwin R.; Haemers, Willem H. (2002), "Spectral characterizations of some distance-regular graphs", Journal of Algebraic Combinatorics, 15 (2): 189–202, doi:10.1023/A:1013847004932, MR 1887234.

Van Maldeghem, Hendrik (2002), "Ten exceptional geometries from trivalent distance regular graphs", Annals of Combinatorics, 6 (2): 209–228, doi:10.1007/PL00012587, MR 1955521, S2CID 195315348.

Read other articles:

Timpano (architettura)

Evidenziato, il frontone del Pantheon di Roma; i suoi geison dentellati racchiudono il timpano In architettura, il timpano è la superficie verticale triangolare racchiusa nella cornice del frontone, i cui tre lati si chiamano geison. I due spioventi sovrastanti i due geison inclinati che concludono l'edificio sono chiamati ciascuno sima. Spesso il timpano era ornato con decorazioni fittili dipinte o sculture oppure, vuoto, era schermato con materiali leggeri, come membrane animali, da cui il...

Kuntul besar

Kuntul Besar Kuntul besar, Ardea alba modesta, pada musim berbiak di Gambus Laut, Lima Puluh Pesisir, Batu Bara, Sumatera Utara Status konservasi LC (IUCN 3.1)[1] Klasifikasi ilmiah Kerajaan: Animalia Filum: Chordata Kelas: Aves Ordo: Pelecaniformes Famili: Ardeidae Genus: Ardea Spesies: Ardea alba Sinonim Casmerodius albus (Linnaeus, 1758) Egretta alba Cramp and Simmons, 1977 Kuntul besar (Ardea alba) adalah spesies burung dari suku Ardeidae. Menghuni pelbagai jenis habitat dar...

Tunapuna–Piarco

RegionTunapuna–Piarco TPRCRegionRegion of Tunapuna–Piarco Coat of armsMotto: Serving the Burgesses of our Region.Location of Tunapuna–Piarco in TrinidadTunapuna–PiarcoCoordinates: 10°38′00″N 61°23′00″W / 10.6333°N 61.3833°W / 10.6333; -61.3833Country Trinidad and TobagoFormer CountiesSaint George CaroniFormer RegionsTunapuna PiarcoCoastlineCaribbean SeaFounded17 July 1992[1]CapitalTunapunaArea • Total527.23 km2 (20...

President of the Continental Congress

Presiding officer of the U.S. Continental Congress President of the United States in Congress AssembledSeal of the president of the CongressContinental CongressStyleMr. President (informal)The Honorable (formal)StatusPresiding officerAppointerVote within the CongressFormationSeptember 5, 1774 (1774-09-05)First holderPeyton RandolphFinal holderCyrus GriffinAbolishedNovember 2, 1788 (1788-11-02) This article is part of a series on theUnited StatesContinental Congre...

KXMX

Radio station in Muldrow, Oklahoma (Fort Smith, Arkansas) For the Anaheim, California radio station that held the call sign KXMX at 1190 AM from 2000 to 2011, see KGBN. KXMXMuldrow, OklahomaBroadcast areaFort Smith, ArkansasFrequency105.1 FM (MHz)BrandingMix 105.1ProgrammingFormatVarietyOwnershipOwnerG2 Media Group LLCTechnical informationFacility ID189538ClassAERP6,000 wattsHAAT98 metersTransmitter coordinates35°30′49″N 94°35′18″W / 35.51364°N 94.58836°W /...

Bilal Coulibaly

Bilal Coulibaly Bilal Coulibaly en 2023. Fiche d’identité Nationalité France Naissance 26 juillet 2004 (19 ans)Saint-Cloud, Hauts-de-Seine Taille 2,03 m (6′ 8″) Poids 88 kg (194 lb) Situation en club Club actuel Wizards de Washington Numéro 0 Poste Ailier Carrière universitaire ou amateur 2012-20172017-2022 Courbevoie Sport BasketLevallois Sporting Club Draft de la NBA Année 2023 Position 7e Franchise Pacers de l'Indiana Carrière professionnelle * SaisonC...

Associazione Calcio Novara 1970-1971

Voce principale: Novara Calcio. AC NovaraStagione 1970-1971 Sport calcio Squadra Novara Allenatore Carlo Parola Comm. straordinario Santino Tarantola Serie B11º Coppa ItaliaSpareggio di qualificazione Maggiori presenzeCampionato: F. Pulici (38)Totale: F. Pulici (42) Miglior marcatoreCampionato: Jacomuzzi (8)Totale: Gabetto, Jacomuzzi (8) 1969-1970 1971-1972 Si invita a seguire il modello di voce Questa voce raccoglie le informazioni riguardanti l'Associazione Calcio Novara nelle co...

大字 (数字)

この項目には、一部のコンピュータや閲覧ソフトで表示できない文字が含まれています（詳細）。数字の大字（だいじ）は、漢数字の一種。通常用いる単純な字形の漢数字（小字）の代わりに同じ音の別の漢字を用いるものである。概要壱万円日本銀行券（「壱」が大字）弐千円日本銀行券（「弐」が大字）漢数字には「一」「二」「三」と続く小字と、「壱」「�...

Balasagun

Ancient Sogdian city in modern-day Kyrgyzstan Not to be confused with Ordu-Baliq. BalasagunKyrgyz: БаласагынThe Burana Tower, at the site of what was once BalasagunShown within KyrgyzstanShow map of KyrgyzstanBalasagun (West and Central Asia)Show map of West and Central AsiaAlternative nameGobalikLocationChüy Region, KyrgyzstanRegionSogdiaCoordinates42°44′49″N 75°14′55″E / 42.74694°N 75.24861°E / 42.74694; 75.24861TypeSettlementHistoryFounded...

ماري ليكي

مارى ليكي معلومات شخصية الميلاد 6 فبراير 1913(1913-02-06)لندن، إنجلترا، المملكة المتحدة الوفاة 9 ديسمبر 1996 (عن عمر ناهز 83 عاماً)نيروبي، كينيا، شرق أفريقيا الجنسية المملكة المتحدة عضوة في الأكاديمية الملكية السويدية للعلوم، والأكاديمية الأمريكية للفنون والعلوم، والأكا�...

Accel World

Accel WorldSampul novel ringan volume pertama, menampilkan Kuroyukihimeアクセル・ワールド(Akuseru Wārudo)GenreAksi, cyberpunk, Roman Novel ringanPengarangReki KawaharaIlustratorHiMAPenerbitASCII Media WorksPenerbit bahasa InggrisNA Yen PressImprintDengeki BunkoMajalahDengeki Bunko MagazineTerbit10 Februari 2009 – sekarangVolume27 MangaPengarangReki KawaharaIlustratorHiroyuki AigamoPenerbitASCII Media WorksPenerbit bahasa InggrisNA Yen PressMajalahDengeki Bunko MagazineDemografiSei...

Hanawa Line

This article relies largely or entirely on a single source. Relevant discussion may be found on the talk page. Please help improve this article by introducing citations to additional sources.Find sources: Hanawa Line – news · newspapers · books · scholar · JSTOR (October 2017) Hanawa LineTrain on the Hanawa Line (photographed in July 2021)OverviewNative name花輪線StatusIn operationOwnerJR EastLocaleIwate, Akita prefecturesTerminiKomaŌdateStations27...

PS Malaka

PS MalakaNama lengkapPersatuan Sepakbola MalakaJulukanManu Meo[1]Berdiri2013; 11 tahun lalu (2013)StadionLapangan Betun, Lapangan Besikama, Std. KobalimaMalaka, Nusa Tenggara TimurPemilikAskab PSSI MalakaManajer Adrianus Bria SeranPelatih Adrianus Bria SeranLigaLiga 3 Kostum kandang Kostum tandang Persatuan Sepakbola Malaka (atau disingkat sebagai PS Malaka) adalah klub sepak bola Indonesia yang berbasis di Kabupaten Malaka, Nusa Tenggara Timur. Mereka saat ini bermain di Liga 3....

Northumbria Healthcare NHS Foundation Trust

State healthcare provider in Northumberland, England, UK Northumbria Healthcare NHS Foundation TrustTypeNHS foundation trustEstablished1 April 1998Hospitals Alnwick Infirmary Berwick Infirmary Blyth Community Hospital Haltwhistle War Memorial Hospital Hexham General Hospital North Tyneside General Hospital Northumbria Specialist Emergency Care Hospital Rothbury Community Hospital Wansbeck General Hospital Staff8,098 FTE (2017/18)[1]Websitewww.northumbria.nhs.uk Northumbria Healthcare ...

تجمع أمصغيرا (مودية)

يفتقر محتوى هذه المقالة إلى الاستشهاد بمصادر. فضلاً، ساهم في تطوير هذه المقالة من خلال إضافة مصادر موثوق بها. أي معلومات غير موثقة يمكن التشكيك بها وإزالتها. (ديسمبر 2018) تجمع أمصغيرا - قرية - تقسيم إداري البلد اليمن المحافظة محافظة أبين المديرية مديرية مودية ا...

Kyu-chan no Dekkai Yume

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Kyu-chan no Dekkai Yume – news · newspapers · books · scholar · JSTOR (February 2022) (Learn how and when to remove this message) 1967 filmKyu-chan no Dekkai YumeDVD coverDirected byYoji YamadaStarringKyu SakamotoChieko BaishoMuga TakewakiShunji SayamaHiroshi I...

الإمارة المزيدية

الإمارة المزيدية بنو مزيد 998 – 1163 إمارة بنو مزيد حوالي 1086 عاصمة الحلة نظام الحكم إمارة اللغة العربية الديانة شيعة أمير علي بن مزيد (الأول) 961–1017 التاريخ الفترة التاريخية حقبة الدولة العباسية التأسيس 998 الزوال 1163 اليوم جزء من العراق ملاحظات تمتعت الإمارة بحكم ذاتي كبي�...

25 травня

← травень → Пн Вт Ср Чт Пт Сб Нд 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 2024 рік 25 травня — 145-й день року (146-й у високосні роки) в григоріанському календарі. До кінця року залишається 220 днів. Цей день в історії: 24 травня—25 травня—26 травня Зміст 1 ...

Kallem-Verri oil field

Kallem-Verri oil fieldLocation of Kallem-Verri oil fieldCountryAlbaniaRegionFier CountyLocationVerriOffshore/onshoreOnshoreCoordinates40°46′N 19°38′E / 40.76°N 19.64°E / 40.76; 19.64Field historyDiscovery1975Start of production1976ProductionEstimated oil in place14.2 million barrels (~1.94×10^6 t)Estimated gas in place0.75×10^9 m3 (26×10^9 cu ft) Kallem-Verri oil field is an Albanian oil field that was discovered in 1975. It is one of the...

سبيد

سبيد الإحداثيات 39°40′37″N 99°25′13″W / 39.6769°N 99.4203°W / 39.6769; -99.4203 [1] تقسيم إداري البلد الولايات المتحدة[2] التقسيم الأعلى مقاطعة فيليبس خصائص جغرافية المساحة 0.380204 كيلومتر مربع (1 أبريل 2010) ارتفاع 568 متر عدد السكان عدد السكان 37 (1 أب...