Barnette–Bosák–Lederberg graph

Barnette–Bosák–Lederberg graph
Vertices38
Edges57
Radius5
Diameter9
Girth4
Chromatic number3
Chromatic index3
PropertiesCubic
Planar
Polyhedral
Table of graphs and parameters

In the mathematical field of graph theory, the Barnette–Bosák–Lederberg graph is a cubic (that is, 3-regular) polyhedral graph with no Hamiltonian cycle, the smallest such graph possible.[1] It was discovered in the mid-1960s by Joshua Lederberg, David Barnette, and Juraj Bosák, after whom it is named. It has 38 vertices and 57 edges.[2][3][4]

Other larger non-Hamiltonian cubic polyhedral graphs include the 46-vertex Tutte graph and a 44-vertex graph found by Emanuels Grīnbergs using Grinberg's theorem. The Barnette–Bosák–Lederberg graph has a similar construction to the Tutte graph but is composed of two Tutte fragments, connected through a pentagonal prism, instead of three connected through a tetrahedron. Without the constraint of having exactly three edges at every vertex, much smaller non-Hamiltonian polyhedral graphs are possible, including the Goldner–Harary graph and the Herschel graph.

References

  1. ^ Holton, D. A.; McKay, B. D. (1988), "The smallest non-Hamiltonian 3-connected cubic planar graphs have 38 vertices", Journal of Combinatorial Theory, Series B, 45 (3): 305–319, doi:10.1016/0095-8956(88)90075-5
  2. ^ Lederberg, Joshua (1967), "Hamilton circuits of convex trivalent polyhedra (up to 18 vertices)", The American Mathematical Monthly, 74 (5): 522–527, doi:10.2307/2314879, JSTOR 2314879, MR 0211895
  3. ^ Bosák, J. (1967), "Hamiltonian lines in cubic graphs", Theory of Graphs (Internat. Sympos., Rome, 1966), New York: Gordon and Breach, pp. 35–46, MR 0221970
  4. ^ Weisstein, Eric W., "Barnette-Bosák-Lederberg Graph", MathWorld

Read other articles:

Neal Burns

Untuk pemain kriket, lihat Neil Burns. Neal BurnsNeal Burns dan Helen Darling dalam A Rambling Romeo (1922)Lahir(1892-06-26)26 Juni 1892Bristol, Pennsylvania, Amerika SerikatMeninggal3 Oktober 1969(1969-10-03) (umur 77)Los Angeles, California, Amerika SerikatPekerjaanPemeran, sutradara, penulisTahun aktif1915-1946 Neal Burns (26 Juni 1892 – 3 Oktober 1969)[1] adalah seorang pemeran, penulis naskah dan sutradara Amerika Serikat. Ia tampil dalam 198 film antara...

 

Elmer Lincoln Irey

First chief of the US IRS, from 1919 to 1943 Elmer Lincoln IreyChief Internal Revenue Service Intelligence UnitIn officeJuly 1, 1919 – January 26, 1943PresidentWoodrow WilsonWarren G. HardingCalvin CoolidgeHerbert HooverFranklin D. RooseveltPreceded byPosition establishedSucceeded byWilliam H. Woolf Personal detailsBorn(1888-03-10)March 10, 1888Kansas City, MODiedJuly 19, 1948(1948-07-19) (aged 60)ResidenceWashington, D.C.Alma materGeorgetown Law School Bachelor of Laws Elmer ...

 

Alfa Romeo Giulia

Alfa Romeo Giulia (Type 105)Alfa Romeo Giulia SuperInformasiProdusenAlfa RomeoMasa produksi1962–1978PerakitanPortello Plant, Milan, Italia (1962–1965)Arese Plant, Arese (MI), Italia (1965–1978)Setúbal, Portugal (Movauto) Willowvale (Salisbury), Zimbabwe (Willowvale Motor Industries)[1]PerancangGiuseppe ScarnatiBodi & rangkaBentuk kerangka4-pintu notchback saloon4-pintu estateTata letakFront-engine, rear-wheel-driveMobil terkaitAlfa Romeo 105/115 Series CoupésAlfa Rome...

Eldridge Cleaver

Eldridge Cleaver nel 1968 Eldridge Cleaver (Wabbaseka, 31 agosto 1935 – Pomona, 1º maggio 1998) è stato un attivista e saggista statunitense, membro importante del Black Panther Party. Negli anni ottanta si avvicinò alle posizioni dei conservatori repubblicani. Indice 1 Biografia 1.1 Soul on Ice 1.2 Le Pantere Nere 1.3 In Francia 1.4 Soul on Fire 1.5 Ritorno negli Stati Uniti 2 Note 3 Altri progetti 4 Collegamenti esterni Biografia Nato a Wabbaseka, nell'Arkansas, Cleaver si trasferì pr...

 

The Lamb (film 1915)

The LambSeena Owen dan Douglas Fairbanks dalam The LambSutradaraW. Christy CabanneSkenarioChristy CabanneCeritaGranville WarwickBerdasarkanThe New Henriettaoleh Bronson Howard, Victor Mapes dan Winchell SmithPemeranDouglas FairbanksSeena OwenSinematograferWilliam E. FildewDistributorTriangle DistributingTanggal rilis 23 September 1915 (1915-09-23) (New York City) 07 November 1915 (1915-11-07) (Seluruh negeri) Durasi56 menitNegaraAmerika SerikatBahasaBisuIntertitel Inggris Th...

 

1st Battalion, 2nd Marines

1st Battalion, 2nd Marines1st Battalion, 2nd Marines insigniaActiveJune 1, 1933 – November 1947October 1949 – presentCountry United States of AmericaBranch United States Marine CorpsTypeInfantryRoleOffense/Defense/Sustainment, Amphibious OperationsPart of2nd Marine Regiment2nd Marine DivisionGarrison/HQMarine Corps Base Camp LejeuneMotto(s)Others will followEngagementsWorld War II Battle of Guadalcanal Battle of Tarawa Battle of Saipan Battle of Tinian Battle of Okinawa Ope...

Alexis Colby

Fictional character on the American TV series Dynasty Soap opera character Alexis ColbyDynasty characterJoan Collins as Alexis ColbyPortrayed byJoan CollinsDuration1981–1989, 1991First appearance The Testimony (1981, non-speaking, face unseen) Enter Alexis (1981) Last appearance Dynasty: The Reunion (1991) Created byRichard and Esther ShapiroSpin-offappearancesDynasty: The Reunion (1991)In-universe informationOther namesAlexis Morell Carrington Colby Dexter RowanOccupati...

 

Files (Google)

File management software FilesOriginal author(s)GoogleDeveloper(s)GoogleInitial releaseDecember 5, 2017; 6 years ago (2017-12-05)Stable release(s)1.3058.618591182.0[1] / March 25, 2024; 30 days ago (2024-03-25) Operating systemAndroidAvailable in90 languagesWebsitefiles.google.com Files (formerly known as Files Go) is a file management app developed by Google for file browsing, media consumption, storage clean-up and offline file transfer. It was re...

 

Darnestown, Maryland

Census-designated place in the United States Census-designated place in MarylandDarnestown, MarylandCensus-designated placeLocation of Darnestown, MarylandCoordinates: 39°07′25″N 77°16′06″W / 39.12361°N 77.26833°W / 39.12361; -77.26833Country United StatesState MarylandCounty MontgomeryArea • Total17.70 sq mi (45.8 km2) • Land16.39 sq mi (42.4 km2) • Water1.31 sq mi (3.4&#...

Kamatero

Municipal unit in GreeceKamatero ΚαματερόMunicipal unit SealKamateroLocation within West Athens regional unit Coordinates: 38°3.583′N 23°42.717′E / 38.059717°N 23.711950°E / 38.059717; 23.711950CountryGreeceAdministrative regionAtticaRegional unitWest AthensMunicipalityAgioi Anargyroi-KamateroArea • Municipal unit5.950 km2 (2.297 sq mi)Elevation160 m (520 ft)Population (2021)[1] • Municipal ...

 

Priory of Sion

French fraternal organization associated with a literary hoax This article has an unclear citation style. The references used may be made clearer with a different or consistent style of citation and footnoting. (October 2020) (Learn how and when to remove this message) The official emblem of the Priory of Sion is partly based on the fleur-de-lis, which was a symbol particularly associated with the French monarchy.[1] The Prieuré de Sion ([pʁi.jœ.ʁe də sjɔ̃]), translated...

 

國際調查記者同盟

此條目可参照英語維基百科相應條目来扩充。 (2021年10月13日)若您熟悉来源语言和主题，请协助参考外语维基百科扩充条目。请勿直接提交机械翻译，也不要翻译不可靠、低品质内容。依版权协议，译文需在编辑摘要注明来源，或于讨论页顶部标记{{Translated page}}标签。 国际调查记者同盟International Consortium of Investigative Journalists成立時間1997年總部华盛顿哥伦比亚特区 地址�...

约翰斯顿环礁

此條目可参照英語維基百科相應條目来扩充。 (2021年5月6日)若您熟悉来源语言和主题，请协助参考外语维基百科扩充条目。请勿直接提交机械翻译，也不要翻译不可靠、低品质内容。依版权协议，译文需在编辑摘要注明来源，或于讨论页顶部标记{{Translated page}}标签。 约翰斯顿环礁Kalama Atoll 美國本土外小島嶼 Johnston Atoll 旗幟颂歌：《星條旗》The Star-Spangled Banner約翰斯頓環礁�...

 

Cirolanidae

Cirolanidae Eurydice pulchra Klasifikasi ilmiah Kerajaan: Animalia Filum: Arthropoda Subfilum: Crustacea Kelas: Malacostraca Ordo: Isopoda Subordo: Cymothoida Superfamili: Cymothooidea Famili: CirolanidaeDana, 1852 [1] Sinonim [1] Bathynomidae Wood Mason & Alcock, 1891 Cirolanidae adalah famili krustasea isopoda, yang terdiri dari predator dan scavenger yang aktif berenang dan memiliki mulut tipe pengigit.[2] Anggota cirolanidae termasuk genera berikut:&...

 

1892 United States presidential election in Washington (state)

Election in Washington Main article: 1892 United States presidential election 1892 United States presidential election in Washington (state) November 8, 1892 1896 →   Nominee Benjamin Harrison Grover Cleveland James B. Weaver Party Republican Democratic Populist Home state Indiana New York Iowa Running mate Whitelaw Reid Adlai E. Stevenson James Field Electoral vote 4 0 0 Popular vote 36,460 29,802 19,165 Percentage 41.45% 33.88% 21.79% County Results Harri...

Republic of the Congo

Country in Central Africa This article is about the smaller country. For the larger country, see Democratic Republic of the Congo. For entities with similar names, see Republic of the Congo (disambiguation). Republic of the Congo République du Congo (French) Republíki ya Kongó (Lingala) Repubilika ya Kôngo (Kituba) Flag Coat of arms Motto: Unité, Travail, Progrès (French)(English: Unity, Work, Progress)Anthem: La Congolaise (French)Besi Kôngo (Ko...

 

Sakai, Osaka

Sakai 堺市Kota terpilihKota Sakai[1]Dari atas kiri: Daisen kofun, Mercusuar Sakai Kuno, Reruntuhan kediaman Rikyu, Ōtori taisha, Myōkoku-ji, Panorama dengan Daisen kofun di bagian tengah BenderaLokasi Sakai di Prefektur OsakaSakaiLokasi di JepangKoordinat: 34°34′24″N 135°28′59″E / 34.57333°N 135.48306°E / 34.57333; 135.48306Koordinat: 34°34′24″N 135°28′59″E / 34.57333°N 135.48306°E / 34.57333; 135.48306NegaraJ...

 

Daftar kecamatan dan kelurahan di Kabupaten Bone

Peta Kabupaten Bone di Sulawesi Selatan Berikut adalah daftar kecamatan dan kelurahan di Kabupaten Bone, Provinsi Sulawesi Selatan, Indonesia. Kabupaten Bone terdiri dari 27 kecamatan, 44 kelurahan dan 328 desa. Pada tahun 2017, kabupaten ini memiliki luas wilayah 4.559,00 km² dan jumlah penduduk sebesar 866.245 jiwa dengan sebaran penduduk 190 jiwa/km².[1][2] Daftar kecamatan [3] dan kelurahan [4] di Kabupaten Bone, adalah sebagai berikut: Kode Kemendagri Ke...

نباتات وعائية

اضغط هنا للاطلاع على كيفية قراءة التصنيف نبات وعائيالعصر: السيلوري–الآن قك ك أ س د ف بر ث ج ط ب ن المرتبة التصنيفية شعبة[1]  التصنيف العلمي النطاق: حقيقيات النوى المملكة: نباتات أصلية غير مصنف: نباتات خضراء غير مصنف: نباتات ملتوية غير مصنف: نباتات جنينية غير مصنف: نباتا...

 

Associazione Calcio Legnano 1986-1987

Voce principale: Associazione Calcio Legnano. A.C. LegnanoStagione 1986-1987Sport calcio Squadra Legnano Allenatore Giovanni Ardemagni Presidente Ulrico Lucarelli poi Giovanni Mari Serie C118º nel girone A. Retrocesso in Serie C2 Coppa Italia Serie C4º nel girone B Maggiori presenzeCampionato: Tirapelle (32) Miglior marcatoreCampionato: Rovellini (4) StadioComunale 1985-1986 1987-1988 Si invita a seguire il modello di voce Questa voce raccoglie le informazioni riguardanti l'Associ...