Flower snark

Flower snark
The flower snarks J3, J5 and J7.
Vertices4n
Edges6n
Girth3 for n=3
5 for n=5
6 for n≥7
Chromatic number3
Chromatic index4
Book thickness3 for n=5
3 for n=7
Queue number2 for n=5
2 for n=7
PropertiesSnark for n≥5
NotationJn with n odd
Table of graphs and parameters
Flower snark J5
The flower snark J5.
Vertices20
Edges30
Girth5
Chromatic number3
Chromatic index4
PropertiesSnark
Hypohamiltonian
Table of graphs and parameters

In the mathematical field of graph theory, the flower snarks form an infinite family of snarks introduced by Rufus Isaacs in 1975.[1]

As snarks, the flower snarks are connected, bridgeless cubic graphs with chromatic index equal to 4. The flower snarks are non-planar and non-Hamiltonian. The flower snarks J5 and J7 have book thickness 3 and queue number 2.[2]

Construction

The flower snark Jn can be constructed with the following process :

  • Build n copies of the star graph on 4 vertices. Denote the central vertex of each star Ai and the outer vertices Bi, Ci and Di. This results in a disconnected graph on 4n vertices with 3n edges (Ai – Bi, Ai – Ci and Ai – Di for 1 ≤ i ≤ n).
  • Construct the n-cycle (B1... Bn). This adds n edges.
  • Finally construct the 2n-cycle (C1... CnD1... Dn). This adds 2n edges.

By construction, the Flower snark Jn is a cubic graph with 4n vertices and 6n edges. For it to have the required properties, n should be odd.

Special cases

The name flower snark is sometimes used for J5, a flower snark with 20 vertices and 30 edges.[3] It is one of 6 snarks on 20 vertices (sequence A130315 in the OEIS). The flower snark J5 is hypohamiltonian.[4]

J3 is a trivial variation of the Petersen graph formed by replacing one of its vertices by a triangle. This graph is also known as the Tietze's graph.[5] In order to avoid trivial cases, snarks are generally restricted to have girth at least 5. With that restriction, J3 is not a snark.

References

  1. ^ Isaacs, R. (1975). "Infinite Families of Nontrivial Trivalent Graphs Which Are Not Tait Colorable". Amer. Math. Monthly. 82: 221–239. doi:10.1080/00029890.1975.11993805. JSTOR 2319844.
  2. ^ Wolz, Jessica; Engineering Linear Layouts with SAT. Master Thesis, University of Tübingen, 2018
  3. ^ Weisstein, Eric W. "Flower Snark". MathWorld.
  4. ^ Weisstein, Eric W. "Hypohamiltonian Graph". MathWorld.
  5. ^ Clark, L.; Entringer, R. (1983), "Smallest maximally nonhamiltonian graphs", Periodica Mathematica Hungarica, 14 (1): 57–68, doi:10.1007/BF02023582.

Read other articles:

Hubungan Indonesia dengan Kamboja

Hubungan Kamboja–Indonesia Kamboja Indonesia Hubungan Indonesia dengan Kamboja mengacu pada hubungan bilateral Kerajaan Kamboja dan Republik Indonesia. Kamboja memiliki kedutaan besar di Jakarta, sementara Indonesia memiliki kedutaan besar di Phnom Penh. Sejak hubungan diplomatik dirintis pada tahun 1960-an. Indonesia selalu mendukung perdamaian dan stabilitas di Kamboja. Indonesia menyediakan pasukan untuk Otoritas Transisi PBB di Kamboja pada tahun 1992, dan pada tahun 1999 Indonesia men...

 

Синелобый амазон

Синелобый амазон Научная классификация Домен:ЭукариотыЦарство:ЖивотныеПодцарство:ЭуметазоиБез ранга:Двусторонне-симметричныеБез ранга:ВторичноротыеТип:ХордовыеПодтип:ПозвоночныеИнфратип:ЧелюстноротыеНадкласс:ЧетвероногиеКлада:АмниотыКлада:ЗавропсидыКласс:Пт�...

 

Eredivisie 2010-2011

Questa voce o sezione sull'argomento Competizioni calcistiche non è ancora formattata secondo gli standard. Commento: Si invita a seguire il modello di voce Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Segui i suggerimenti del progetto di riferimento. Eredivisie 2010-2011 Competizione Eredivisie Sport Calcio Edizione 55ª Organizzatore Federazione calcistica dei Paesi Bassi Date dal 6 agosto 2010al 15 maggio 2011 Luogo  Paesi Bassi Partecipanti 18 Risult...

Iltutmish

13th century ruler of the Delhi Sultinate Shams-ud-Din IltutmishSultanIlltumish Tomb in Qutub Minar Complex3rd Sultan of DelhiReignJune 1211 – 30 April 1236PredecessorAram ShahSuccessorRukn ud din FiruzBornunknownCentral Asia[1]Died30 April 1236Delhi, Delhi SultanateBurialQutb Complex, Mehrauli, DelhiSpousesTurkan Khatun, a daughter of Qutub-ud-din Aibak (Chief consort)[2][non-primary source needed] Shah Turkan Malikah-i-Jahan[3][non-primary source needed...

 

David Beckham

English footballer (born 1975) David BeckhamOBEBeckham at the 2014 Wimbledon ChampionshipsBornDavid Robert Joseph Beckham (1975-05-02) 2 May 1975 (age 49)London, EnglandOccupations Footballer Businessman Organisation(s)UNICEF, Malaria No More[1]AgentSimon Fuller (XIX Entertainment)Height6 ft 0 in (1.83 m)[2][3][4]Spouse Victoria Adams ​(m. 1999)​Children4, including Brooklyn and RomeoRelativesNicola Peltz (daught...

 

雅克·希拉克

此條目翻譯品質不佳。翻譯者可能不熟悉中文或原文語言，也可能使用了機器翻譯。請協助翻譯本條目或重新編寫，并注意避免翻译腔的问题。明顯拙劣的翻譯請改掛{{d|G13}}提交刪除。  「希拉克」重定向至此。關於法国洛泽尔省的同名市镇，請見「希拉克 (洛泽尔省)」。 雅克·勒内·希拉克Jacques René Chirac 第22任法國總統安道爾大公任期1995年5月17日—2007年5月16日...

Насилие в отношении мирного населения Германии в конце Второй мировой войны

Карта территориальных изменений и оккупационных зон в Германии после 1945 г. На заключительном этапе Второй мировой войны военными силами антигитлеровской коалиции[1] были совершены акты насилия в отношении мирного населения Германии[2]. Так как после окончания в�...

 

2020年夏季奧林匹克運動會波蘭代表團

2020年夏季奥林匹克运动会波兰代表團波兰国旗IOC編碼POLNOC波蘭奧林匹克委員會網站olimpijski.pl（英文）（波兰文）2020年夏季奥林匹克运动会（東京）2021年7月23日至8月8日（受2019冠状病毒病疫情影响推迟，但仍保留原定名称）運動員206參賽項目24个大项旗手开幕式：帕维尔·科热尼奥夫斯基（游泳）和马娅·沃什乔夫斯卡（自行车）[1]闭幕式：卡罗利娜·纳亚（皮划艇）&#...

 

Навчально-науковий інститут інноваційних освітніх технологій Західноукраїнського національного університету

Навчально-науковий інститут інноваційних освітніх технологій Західноукраїнського національного університету Герб навчально-наукового інституту інноваційних освітніх технологій ЗУНУ Скорочена назва ННІІОТ ЗУНУ Основні дані Засновано 2013 Заклад Західноукраїнський �...

中華民國國軍中的中共間諜列表

 本表是動態列表，或許永遠不會完結。歡迎您參考可靠來源來查漏補缺。 潛伏於中華民國國軍中的中共間諜列表收錄根據公開資料來源，曾潛伏於中華民國國軍、被中國共產黨聲稱或承認，或者遭中華民國政府調查審判，為中華人民共和國和中國人民解放軍進行間諜行為的人物。以下列表以現今可查知時間為準，正確的間諜活動或洩漏機密時間可能早於或晚於以下所歸�...

 

Helen Prejean

Death penalty abolition advocate SisterHelen PrejeanCSJPrejean in 2006Born (1939-04-21) April 21, 1939 (age 85)Baton Rouge, Louisiana, U.S.EducationSt. Mary's Dominican CollegeSaint Paul UniversityOccupation(s)Sister, spiritual adviser, author, anti-death penalty activist Helen Prejean CSJ (/preɪˈʒɑːn/ pray-ZHAHN;[1] born April 21, 1939) is a Catholic religious sister and a leading American advocate for the abolition of the death penalty. She is known for her best-selling bo...

 

Argentina en la Copa Mundial de Fútbol de 2018

Argentina 16.to puesto Titular Alternativo Datos generales Asociación AFA Confederación Conmebol Seudónimo Albiceleste Ranking FIFA 5.to lugar (junio de 2018) Participación 17.ª Mejor resultado Campeón (1978, 1986) Entrenador Jorge Sampaoli Estadísticas Partidos 4 Goles anotados 6 (1.5 por partido) Goles recibidos 9 (2.25 por partido) Goleador Sergio Agüero (2 goles) Cronología Anterior Brasil 2014 Siguiente Catar 2022 La selección de Argentina fue uno de los 32 equipos participant...

قائمة المدن التوأمة في مصر

المدن التوأمة في مصر هو الاتفاق بين مدينتين على التعاون في مختلف المجالات والأمور التي تعني التجمعات السكنية المدنية. وهي اتفاقية تعاون بين مدينتين، يوقع عليها عادة صاحب أعلى سلطة في كلا المدينتين. يقوم فريق من كلا المدينتين بإعداد بنود الاتفاقية. في الوطن العربي ترعى منظ�...

 

Anglo-Egyptian Sudan

1899–1956 period of Anglo-Egyptian rule This article is about the administration of the Sudan between 1899 and 1956. For its history during the same period, see History of Anglo-Egyptian Sudan. 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: Anglo-Egyptian Sudan – news · newspapers · books · scholar · JSTO...

 

Trams in Huai'an

Trams in Huai'anOverviewNative name淮安现代有轨电车LocaleHuai'an, ChinaTransit typeTramNumber of lines1Number of stations23Daily ridership27,000 (2019 daily avg.) 55,000 (2019 record)[1]Websitehttp://www.hatram.com/OperationBegan operation28 December 2015; 8 years ago (2015-12-28)Operator(s)Huai'an Modern Tram Operation Co., Ltd.TechnicalSystem length20.07 km (12.47 mi)[2]Track gaugeStandard gauge 1,435 mm (4 ft 8+1⁄...

Dewayne Staats

American sportscaster (born 1952) Dewayne StaatsStaats in 2009Born (1952-08-08) August 8, 1952 (age 71)Advance, Missouri, U.S.[1]Sports commentary careerTeam(s)Houston Astros (1977-84)Chicago Cubs (1985-89)New York Yankees (1990-94)Tampa Bay Rays (1998-present)GenrePlay-by-playSportMajor League Baseball Dewayne Staats (born August 8, 1952)[2][3] is an American sports broadcaster who has been the television play-by-play commentator for the Tampa Bay Rays since thei...

 

3月8日

<< 2024年3月 >> 日 一 二 三 四 五 六 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年 2023年 2022年 3月8日是公历一年中的第67天（闰年第68天），离全年的结束还有298天。 大事记 18世紀前 1010年：波斯詩人菲爾多西完成紀錄神話傳說到薩珊王朝歷史的民族史詩《列王紀》。 1576年：一名西班牙殖民官員給菲利普二世寫了一封信，信中首...

 

Major League Soccer 2002

Major League Soccer Saison 2002 Généralités Sport football (soccer) Organisateur(s) Major League Soccer Édition 7e Lieu(x) États-Unis Date Saison régulière :23 mars au 22 sept. 2002 Séries éliminatoires : 25 sept. au 20 oct. 2002 Nations États-Unis Participants 10 franchises Épreuves 140 matchs + séries éliminatoires Affluence 2 214 978 spectateurs soit 15 821 par match (saison régulière) Site(s) Finale au Gillette Stadium de Foxborough Site web officiel ht...

Fort Kent, Maine

Town in Maine, United StatesFort Kent Fort-KentTownTown of Fort KentVille de Fort-Kent (French)The Fort Kent Railroad Station is listed on the National Register of Historic PlacesMotto: The Little Town That Could[1]Location of Fort Kent, MaineFort KentLocation of Fort Kent in MaineShow map of MaineFort KentLocation of Fort Kent in the USAShow map of the United StatesCoordinates: 47°14′31″N 68°34′20″W / 47.24194°N 68.57222°W / 47.24194; -6...

 

ЗУР семейства «Стандарт»

ПУ Mk. 26 с ракетой RIM-66 Standard missile (SM-2 MR) на борту крейсера USS Ticonderoga Пуск ракеты Standard Missile (SM-1) с эсминца УРО USS Sampson в районе Пуэрто-Рико Standard — семейство американских твердотопливных зенитных управляемых ракет класса «корабль — воздух», средней и большой дальности. До 1992 �...