Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

Граф Халіна у теорії графів є типом планарного графу який будується з єднанням листя дерева у цикл Дерево повинне мати щ

Граф Халіна

Граф Халіна

Граф Халіна у теорії графів є типом планарного графу, який будується з'єднанням листя дерева у цикл. Дерево повинне мати щонайменше чотири вершини, жодна з яких не має рівно двох сусідів; воно повинно бути намальовано в площині, так що жодні з його ребер не перетинаються (це називається плоским вкладенням), і цикл з'єднує листки за годинниковою стрілкою у цьому вкладенні. Таким чином, цикл утворює зовнішню грань графа Халіна, яка містить дерево всередині.

image
Граф Халіна.

Графи Халіна названі на честь німецького математика [en], який вивчав їх у 1971 році, але кубічні графи Халіна — ті, в яких кожна вершина з'єднує рівно три ребра — вже більш ніж століття тому досліджувались [en]. Вони є багатогранними графами, що означає, що кожен граф Халіна може бути використаний для утворення вершин та ребер опуклих багатогранників, а багатогранники, утворені з них, отримали назву багатогранників без даху (англ. roofless polyhedra) або куполів (англ. domes).

Кожен граф Халіна має цикл Гамільтона, що проходить через всі його вершини, а також цикли майже всіх довжин відповідно до кількості вершин. Графи Халіна можуть бути визначені за лінійний час. Оскільки графи Халіна мають невелику ширину дерева, багато обчислювальних задач, які є складними у випадку інших видів планарних графів, таких як пошук циклу Гамільтона, можуть бути швидко розв'язані на графах Халіна.

image
Трикутна призма, побудована як граф Халіна з 6-вершинного дерева.

Приклади

image
Колеса.

Зірка — дерево з рівно однією внутрішньою вершиною. Застосування побудови графа Халіна до зірки створює колесо, граф складений з ребер піраміди. Граф трикутної призми також є графом Халіна: він може бути зображений так, що одна з його прямокутних граней — буде зовнішнім циклом, а інші ребра утворюють дерево з чотирма листками, двома внутрішніми вершинами та п'ятьма ребрами.

Граф Фрухта, один з двох найменших кубічних графів, що не містить нетривіальних автоморфізмів графів, також є графом Халіна.

Властивості

Будь-який граф Халіна 3-зв'язний, що означає, що не можна розбити граф на два графи шляхом видалення двох вершин. Він також реберно мінімально 3-зв'язний, що означає, що після видалення будь-якого ребра граф перестає бути 3-зв'язний. Відповідно до теореми Штайніца, як 3-зв'язний планарний граф, граф Халіна можна представити у вигляді множини вершин і ребер опуклого багатогранника, тобто він є поліедральним графом. Отже, як і для будь якого графу багатогранника, його вкладення в площину буде єдиним з точністю до вибору грані, яка буде його зовнішньою гранню.

Кожен граф Халіна є Гамільтоновим графом і будь-яке ребро належить циклу Гамільтона. Більш того, кожен граф Халіна залишається Гамільтоновим після видалення будь-якої вершини. Оскільки будь-яке дерево без вершин ступеня 2 містить два листи зі спільним батьком, будь-який граф Халіна містить трикутник. Зокрема, граф Халіна не може бути ні графом без трикутників, ні двочастковим графом.

image
Граф Халіна без циклу довжини 8. Подібна побудова дозволяє уникнути циклів заданої парної довжини.

Більш строго, кожен граф Халіна є майже панциклічним, в тому сенсі, що він має цикли всіх довжин від 3 до n з можливим винятком одного циклу парної довжини. Більш того, будь-який граф Халіна залишається майже панциклічним після стягування одного ребра, і будь-який граф Халіна без внутрішніх вершин степеня три є панциклічним.

[en] графу Халіна з максимальним степенем Δ(G) більшим ніж чотири буде Δ(G) + 1. Це число кольорів потрібне для розфарбування всіх пар (v,e), де v — вершина графу, а e — ребро інцидентне v, при певних обмеженях на фарбування. Пари які мають спільну вершину або ребро не можуть бути однакового кольору. Додатково, пара (v,e) не може мати колір однаковий з парою, у якої один кінець належить e. Для графів Халіна з Δ(G) = 3 або 4, інцидентне хроматичне число може бути 5 або 6 відповідно.

Обчислювальна складність

За лінійний час можливо перевірити чи буде заданий n-вершинний граф графом Халіна, якщо шукати його планарне вкладення, і, якщо воно існує, то перевірити, чи знайдеться грань з щонайменше n/2 + 1 вершиною, кожна з яких буде степені три. Якщо так, то може бути не більше чотирьох таких граней, і можна перевірити за лінійний час для кожної з них, чи буде решта графу утворювати дерево з вершинами цієї грані у якості листків. Якщо таких граней немає, то граф не буде графом Халіна. Альтернативно, граф з n вершинами та m ребрами буде графом Халіна тоді, і тільки тоді, коли він планарний, 3-зв'язний і має грань у якої число вершин дорівнює цикломатичному числу графа m − n + 1. Все з цього можна перевірити за лінійний час. Інші методи перевірки, які виконуються за лінійний час, або використовують теорему Курселя або [en], для жодного з них не потрібно з'ясовувати чи існує плоске вкладання графу.

Будь-який граф Халіна має ширину дерева три. Тому багато задач оптимізації, які є NP-повними для довільних графів, наприклад, така як пошук (максимальної незалежної множини), для графів Халіна можна розв'язати за лінійний час при використанні динамічного програмування або при використанні теореми Курселя або у деяких випадках (таких, як побудова Гамільтонова циклу) прямими алгоритмами. Однак, задача пошуку найбільшого підграфу Халіна у довільному графі є NP-складною, бо потрібно перевірити, чи існує підграф Халіна, який включає всі вершини заданого графа, або перевірити, чи даний граф є підграфом більшого графу Халіна.

Історія

В 1971 році Халін ввів ці графи як клас мінімальних 3-вершинних зв'язних графів: для кожного ребра графу, видалення цього ребра зменшує зв'язність графу. Ці графи набули значущості, коли стало зрозуміло, що багато алгоритмічних задач, які неможливо обчислити для довільних планарних графів, можна ефективно розв'язати для них. Цей факт пізніше був пояснений як наслідок незначної ширини їх дерева та алгоритмічними мета-теоремами, такими як теорема Курселя, які забезпечують ефективне роз'язання таких задач на будь-якому графі з незначною шириною дерева.

До роботи Халіна по цім графам, задачи перерахування графів щодо кубічних (або 3-регулярних) графів Халіна досліджувались у 1856 році [en] і в 1965 році [en]. Радемахер називав ці графи побудованими на багатокутнику. Він визначав їх як кубічний поліедральний граф з f гранями, з яких одна має f − 1 ребро. Графи, які підходять під це визначення, саме і є кубічними графами Халіна.

Натхненні тим, що як графи Халіна, так і 4-вершинно-зв'язні планарні графи містять гамільтонові цикли, Lovász та Plummer, (1974) припустили, що кожен 4-вершинно-зв'язний планарний граф містить з'єднуючий підграф Халіна; тут «з'єднуючий» (англ. spanning) означає, що підграф містить усі вершини більшого графу. Гіпотеза Lovász–Plummer залишалась не розв'язаною до 2015 роу, поки не було знайдено спосіб побудови нескінченної кількості контрприкладів.

Інколи графи Халіна називають «огороженими деревами» (англ. skirted trees) або «полієдрами без даху» (англ. roofless polyhedra). Проте такі назви неоднозначні. Деякі автори використовують назву «огорожені дерева» для планарних графів утворених з дерев, листя яких об'єднано у цикл, без вимоги, щоб внутрішні вершими були степені три або більше. Назви на кшталт «побудовані на багатокутнику» або «полієдри без даху» можуть вказувати на кубічні графи Халіна. Опуклі полієдри, чиї графи є графами Халіна інколи називають «куполами» (англ. domes).

Примітки

  1. Encyclopaedia of Mathematics, first Supplementary volume, 1988, , p. 281, article «Halin Graph» [ 11 січня 2014 у Wayback Machine.], and references therein.
  2. (1971), Studies on minimally n-connected graphs, Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969), London: Academic Press, с. 129—136, MR 0278980.
  3. тобто, степінь вершини буде 3
  4. (1856), On the enumeration of x-edra having triedral summits and an (x − 1)-gonal base, Philosophical Transactions of the Royal Society of London: 399—411, doi:10.1098/rstl.1856.0018, JSTOR 108592.
  5. Cornuéjols, Naddef та Pulleyblank, (1983): «If T is a star, i.e., a single node v joined to n other nodes, then H is called a wheel and is the simplest type of Halin graph.»
  6. See Sysło та Proskurowski, (1983), Prop. 4.3, p. 254, which identifies the triangular prism as the unique graph with exactly three cycles that can be the outer cycle of a realization as a Halin graph.
  7. Weisstein, Eric W. Halin Graph(англ.) на сайті Wolfram MathWorld.
  8. ; Naddef, D.; (1983), Halin graphs and the travelling salesman problem, , 26 (3): 287—294, doi:10.1007/BF02591867.
  9. See the proof of Theorem 10 in Wang, Weifan; Bu, Yuehua; Montassier, Mickaël; Raspaud, André (2012), On backbone coloring of graphs, Journal of Combinatorial Optimization, 23 (1): 79—93, doi:10.1007/s10878-010-9342-6, MR 2875236: «Since G contains a 3-cycle consisting of one inner vertex and two outer vertices, G is not a bipartite graph.»
  10. Malkevitch, Joseph (1978), Cycle lengths in polytopal graphs, Theory and applications of graphs (Proc. Internat. Conf., Western Mich. Univ., Kalamazoo, Mich., 1976), Berlin: Springer, 642: 364—370, doi:10.1007/BFb0070393, MR 0491287
  11. Skowrońska, Mirosława (1985), The pancyclicity of Halin graphs and their exterior contractions, у ; (ред.), Cycles in Graphs, Annals of Discrete Mathematics, т. 27, Elsevier Science Publishers B.V., с. 179—194.
  12. Wang, Shu-Dong; Chen, Dong-Ling; Pang, Shan-Chen (2002), The incidence coloring number of Halin graphs and outerplanar graphs, , 256 (1-2): 397—405, doi:10.1016/S0012-365X(01)00302-8, MR 1927561.
  13. Shiu, W. C.; Sun, P. K. (2008), Invalid proofs on incidence coloring, , 308 (24): 6575—6580, doi:10.1016/j.disc.2007.11.030, MR 2466963.
  14. Fomin, Fedor V.; Thilikos, Dimitrios M. (2006), A 3-approximation for the pathwidth of Halin graphs, Journal of Discrete Algorithms, 4 (4): 499—510, doi:10.1016/j.jda.2005.06.004, MR 2577677.
  15. Sysło, Maciej M.; Proskurowski, Andrzej (1983), On Halin graphs, Graph Theory: Proceedings of a Conference held in Lagów, Poland, February 10–13, 1981, Lecture Notes in Mathematics, т. 1018, Springer-Verlag, с. 248—256, doi:10.1007/BFb0071635.
  16. Eppstein, David (2016), Simple recognition of Halin graphs and their generalizations, , 20 (2): 323—346, arXiv:1502.05334, doi:10.7155/jgaa.00395.
  17. (1988), (PDF), Technical Report RUU-CS-88-14, Department of Computer Science, Utrecht University, архів оригіналу (PDF) за 28 липня 2004 {{}}: Cite має пустий невідомий параметр: |df= ().
  18. (1988), Dynamic programming on graphs with bounded treewidth, Proceedings of the 15th International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science, т. 317, Springer-Verlag, с. 105—118, doi:10.1007/3-540-19488-6_110, ISBN .
  19. Horton, S. B.; Parker, R. Gary (1995), On Halin subgraphs and supergraphs, , 56 (1): 19—35, doi:10.1016/0166-218X(93)E0131-H, MR 1311302.
  20. (1965), , Illinois Journal of Mathematics, 9: 361—380, MR 0179682, архів оригіналу за 24 липня 2018, процитовано 24 липня 2018.
  21. Chen, Guantao; Enomoto, Hikoe; Ozeki, Kenta; Tsuchiya, Shoichi (2015), Plane triangulations without a spanning Halin subgraph: counterexamples to the Lovász-Plummer conjecture on Halin graphs, SIAM Journal on Discrete Mathematics, 29 (3): 1423—1426, doi:10.1137/140971610, MR 3376776.
  22. Skowrońska, M.; Sysło, M. M. (1987), Hamiltonian cycles in skirted trees, Proceedings of the International Conference on Combinatorial Analysis and its Applications (Pokrzywna, 1985), Polska Akademia Nauk, 19 (3-4): 599–610 (1988), MR 0951375
  23. Lovász, L.; (1974), On a family of planar bicritical graphs, Combinatorics (Proc. British Combinatorial Conf., Univ. Coll. Wales, Aberystwyth, 1973), London: Cambridge Univ. Press, с. 103–107. London Math. Soc. Lecture Note Ser., No. 13, MR 0351915.
  24. Demaine, Erik D.; ; Uehara, Ryuhei (2013), Zipper unfolding of domes and prismoids, , с. 43—48, архів оригіналу за 24 липня 2018, процитовано 24 липня 2018.

Посилання

  • , Інформаційна система про включення класів графів.
  • Weisstein, Eric W. Halin Graph(англ.) на сайті Wolfram MathWorld.
  • Wang, Shu-Dong; Chen, Dong-Ling; Pang, Shan-Chen (2002), The incidence coloring number of Halin graphs and outerplanar graphs, , 256 (1-2): 397—405, doi:10.1016/S0012-365X(01)00302-8, MR 1927561

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

Graf Halina u teoriyi grafiv ye tipom planarnogo grafu yakij buduyetsya z yednannyam listya dereva u cikl Derevo povinne mati shonajmenshe chotiri vershini zhodna z yakih ne maye rivno dvoh susidiv vono povinno buti namalovano v ploshini tak sho zhodni z jogo reber ne peretinayutsya ce nazivayetsya ploskim vkladennyam i cikl z yednuye listki za godinnikovoyu strilkoyu u comu vkladenni Takim chinom cikl utvoryuye zovnishnyu gran grafa Halina yaka mistit derevo vseredini Graf Halina Grafi Halina nazvani na chest nimeckogo matematika en yakij vivchav yih u 1971 roci ale kubichni grafi Halina ti v yakih kozhna vershina z yednuye rivno tri rebra vzhe bilsh nizh stolittya tomu doslidzhuvalis en Voni ye bagatogrannimi grafami sho oznachaye sho kozhen graf Halina mozhe buti vikoristanij dlya utvorennya vershin ta reber opuklih bagatogrannikiv a bagatogranniki utvoreni z nih otrimali nazvu bagatogrannikiv bez dahu angl roofless polyhedra abo kupoliv angl domes Kozhen graf Halina maye cikl Gamiltona sho prohodit cherez vsi jogo vershini a takozh cikli majzhe vsih dovzhin vidpovidno do kilkosti vershin Grafi Halina mozhut buti viznacheni za linijnij chas Oskilki grafi Halina mayut neveliku shirinu dereva bagato obchislyuvalnih zadach yaki ye skladnimi u vipadku inshih vidiv planarnih grafiv takih yak poshuk ciklu Gamiltona mozhut buti shvidko rozv yazani na grafah Halina Trikutna prizma pobudovana yak graf Halina z 6 vershinnogo dereva PrikladiKolesa Zirka derevo z rivno odniyeyu vnutrishnoyu vershinoyu Zastosuvannya pobudovi grafa Halina do zirki stvoryuye koleso graf skladenij z reber piramidi Graf trikutnoyi prizmi takozh ye grafom Halina vin mozhe buti zobrazhenij tak sho odna z jogo pryamokutnih granej bude zovnishnim ciklom a inshi rebra utvoryuyut derevo z chotirma listkami dvoma vnutrishnimi vershinami ta p yatma rebrami Graf Fruhta odin z dvoh najmenshih kubichnih grafiv sho ne mistit netrivialnih avtomorfizmiv grafiv takozh ye grafom Halina VlastivostiBud yakij graf Halina 3 zv yaznij sho oznachaye sho ne mozhna rozbiti graf na dva grafi shlyahom vidalennya dvoh vershin Vin takozh reberno minimalno 3 zv yaznij sho oznachaye sho pislya vidalennya bud yakogo rebra graf perestaye buti 3 zv yaznij Vidpovidno do teoremi Shtajnica yak 3 zv yaznij planarnij graf graf Halina mozhna predstaviti u viglyadi mnozhini vershin i reber opuklogo bagatogrannika tobto vin ye poliedralnim grafom Otzhe yak i dlya bud yakogo grafu bagatogrannika jogo vkladennya v ploshinu bude yedinim z tochnistyu do viboru grani yaka bude jogo zovnishnoyu grannyu Kozhen graf Halina ye Gamiltonovim grafom i bud yake rebro nalezhit ciklu Gamiltona Bilsh togo kozhen graf Halina zalishayetsya Gamiltonovim pislya vidalennya bud yakoyi vershini Oskilki bud yake derevo bez vershin stupenya 2 mistit dva listi zi spilnim batkom bud yakij graf Halina mistit trikutnik Zokrema graf Halina ne mozhe buti ni grafom bez trikutnikiv ni dvochastkovim grafom Graf Halina bez ciklu dovzhini 8 Podibna pobudova dozvolyaye uniknuti cikliv zadanoyi parnoyi dovzhini Bilsh strogo kozhen graf Halina ye majzhe panciklichnim v tomu sensi sho vin maye cikli vsih dovzhin vid 3 do n z mozhlivim vinyatkom odnogo ciklu parnoyi dovzhini Bilsh togo bud yakij graf Halina zalishayetsya majzhe panciklichnim pislya styaguvannya odnogo rebra i bud yakij graf Halina bez vnutrishnih vershin stepenya tri ye panciklichnim en grafu Halina z maksimalnim stepenem D G bilshim nizh chotiri bude D G 1 Ce chislo koloriv potribne dlya rozfarbuvannya vsih par v e de v vershina grafu a e rebro incidentne v pri pevnih obmezhenyah na farbuvannya Pari yaki mayut spilnu vershinu abo rebro ne mozhut buti odnakovogo koloru Dodatkovo para v e ne mozhe mati kolir odnakovij z paroyu u yakoyi odin kinec nalezhit e Dlya grafiv Halina z D G 3 abo 4 incidentne hromatichne chislo mozhe buti 5 abo 6 vidpovidno Obchislyuvalna skladnistZa linijnij chas mozhlivo pereviriti chi bude zadanij n vershinnij graf grafom Halina yaksho shukati jogo planarne vkladennya i yaksho vono isnuye to pereviriti chi znajdetsya gran z shonajmenshe n 2 1 vershinoyu kozhna z yakih bude stepeni tri Yaksho tak to mozhe buti ne bilshe chotiroh takih granej i mozhna pereviriti za linijnij chas dlya kozhnoyi z nih chi bude reshta grafu utvoryuvati derevo z vershinami ciyeyi grani u yakosti listkiv Yaksho takih granej nemaye to graf ne bude grafom Halina Alternativno graf z n vershinami ta m rebrami bude grafom Halina todi i tilki todi koli vin planarnij 3 zv yaznij i maye gran u yakoyi chislo vershin dorivnyuye ciklomatichnomu chislu grafa m n 1 Vse z cogo mozhna pereviriti za linijnij chas Inshi metodi perevirki yaki vikonuyutsya za linijnij chas abo vikoristovuyut teoremu Kurselya abo en dlya zhodnogo z nih ne potribno z yasovuvati chi isnuye ploske vkladannya grafu Bud yakij graf Halina maye shirinu dereva tri Tomu bagato zadach optimizaciyi yaki ye NP povnimi dlya dovilnih grafiv napriklad taka yak poshuk maksimalnoyi nezalezhnoyi mnozhini dlya grafiv Halina mozhna rozv yazati za linijnij chas pri vikoristanni dinamichnogo programuvannya abo pri vikoristanni teoremi Kurselya abo u deyakih vipadkah takih yak pobudova Gamiltonova ciklu pryamimi algoritmami Odnak zadacha poshuku najbilshogo pidgrafu Halina u dovilnomu grafi ye NP skladnoyu bo potribno pereviriti chi isnuye pidgraf Halina yakij vklyuchaye vsi vershini zadanogo grafa abo pereviriti chi danij graf ye pidgrafom bilshogo grafu Halina IstoriyaV 1971 roci Halin vviv ci grafi yak klas minimalnih 3 vershinnih zv yaznih grafiv dlya kozhnogo rebra grafu vidalennya cogo rebra zmenshuye zv yaznist grafu Ci grafi nabuli znachushosti koli stalo zrozumilo sho bagato algoritmichnih zadach yaki nemozhlivo obchisliti dlya dovilnih planarnih grafiv mozhna efektivno rozv yazati dlya nih Cej fakt piznishe buv poyasnenij yak naslidok neznachnoyi shirini yih dereva ta algoritmichnimi meta teoremami takimi yak teorema Kurselya yaki zabezpechuyut efektivne roz yazannya takih zadach na bud yakomu grafi z neznachnoyu shirinoyu dereva Do roboti Halina po cim grafam zadachi pererahuvannya grafiv shodo kubichnih abo 3 regulyarnih grafiv Halina doslidzhuvalis u 1856 roci en i v 1965 roci en Rademaher nazivav ci grafi pobudovanimi na bagatokutniku Vin viznachav yih yak kubichnij poliedralnij graf z f granyami z yakih odna maye f 1 rebro Grafi yaki pidhodyat pid ce viznachennya same i ye kubichnimi grafami Halina Nathnenni tim sho yak grafi Halina tak i 4 vershinno zv yazni planarni grafi mistyat gamiltonovi cikli Lovasz ta Plummer 1974 pripustili sho kozhen 4 vershinno zv yaznij planarnij graf mistit z yednuyuchij pidgraf Halina tut z yednuyuchij angl spanning oznachaye sho pidgraf mistit usi vershini bilshogo grafu Gipoteza Lovasz Plummer zalishalas ne rozv yazanoyu do 2015 rou poki ne bulo znajdeno sposib pobudovi neskinchennoyi kilkosti kontrprikladiv Inkoli grafi Halina nazivayut ogorozhenimi derevami angl skirted trees abo poliyedrami bez dahu angl roofless polyhedra Prote taki nazvi neodnoznachni Deyaki avtori vikoristovuyut nazvu ogorozheni dereva dlya planarnih grafiv utvorenih z derev listya yakih ob yednano u cikl bez vimogi shob vnutrishni vershimi buli stepeni tri abo bilshe Nazvi na kshtalt pobudovani na bagatokutniku abo poliyedri bez dahu mozhut vkazuvati na kubichni grafi Halina Opukli poliyedri chiyi grafi ye grafami Halina inkoli nazivayut kupolami angl domes PrimitkiEncyclopaedia of Mathematics first Supplementary volume 1988 ISBN 0 7923 4709 9 p 281 article Halin Graph 11 sichnya 2014 u Wayback Machine and references therein 1971 Studies on minimally n connected graphs Combinatorial Mathematics and its Applications Proc Conf Oxford 1969 London Academic Press s 129 136 MR 0278980 tobto stepin vershini bude 3 1856 On the enumeration of x edra having triedral summits and an x 1 gonal base Philosophical Transactions of the Royal Society of London 399 411 doi 10 1098 rstl 1856 0018 JSTOR 108592 Cornuejols Naddef ta Pulleyblank 1983 If T is a star i e a single node v joined to n other nodes then H is called a wheel and is the simplest type of Halin graph See Syslo ta Proskurowski 1983 Prop 4 3 p 254 which identifies the triangular prism as the unique graph with exactly three cycles that can be the outer cycle of a realization as a Halin graph Weisstein Eric W Halin Graph angl na sajti Wolfram MathWorld Naddef D 1983 Halin graphs and the travelling salesman problem 26 3 287 294 doi 10 1007 BF02591867 See the proof of Theorem 10 in Wang Weifan Bu Yuehua Montassier Mickael Raspaud Andre 2012 On backbone coloring of graphs Journal of Combinatorial Optimization 23 1 79 93 doi 10 1007 s10878 010 9342 6 MR 2875236 Since G contains a 3 cycle consisting of one inner vertex and two outer vertices G is not a bipartite graph Malkevitch Joseph 1978 Cycle lengths in polytopal graphs Theory and applications of graphs Proc Internat Conf Western Mich Univ Kalamazoo Mich 1976 Berlin Springer 642 364 370 doi 10 1007 BFb0070393 MR 0491287 Skowronska Miroslawa 1985 The pancyclicity of Halin graphs and their exterior contractions u red Cycles in Graphs Annals of Discrete Mathematics t 27 Elsevier Science Publishers B V s 179 194 Wang Shu Dong Chen Dong Ling Pang Shan Chen 2002 The incidence coloring number of Halin graphs and outerplanar graphs 256 1 2 397 405 doi 10 1016 S0012 365X 01 00302 8 MR 1927561 Shiu W C Sun P K 2008 Invalid proofs on incidence coloring 308 24 6575 6580 doi 10 1016 j disc 2007 11 030 MR 2466963 Fomin Fedor V Thilikos Dimitrios M 2006 A 3 approximation for the pathwidth of Halin graphs Journal of Discrete Algorithms 4 4 499 510 doi 10 1016 j jda 2005 06 004 MR 2577677 Syslo Maciej M Proskurowski Andrzej 1983 On Halin graphs Graph Theory Proceedings of a Conference held in Lagow Poland February 10 13 1981 Lecture Notes in Mathematics t 1018 Springer Verlag s 248 256 doi 10 1007 BFb0071635 Eppstein David 2016 Simple recognition of Halin graphs and their generalizations 20 2 323 346 arXiv 1502 05334 doi 10 7155 jgaa 00395 1988 PDF Technical Report RUU CS 88 14 Department of Computer Science Utrecht University arhiv originalu PDF za 28 lipnya 2004 a href wiki D0 A8 D0 B0 D0 B1 D0 BB D0 BE D0 BD Citation title Shablon Citation citation a Cite maye pustij nevidomij parametr df dovidka 1988 Dynamic programming on graphs with bounded treewidth Proceedings of the 15th International Colloquium on Automata Languages and Programming Lecture Notes in Computer Science t 317 Springer Verlag s 105 118 doi 10 1007 3 540 19488 6 110 ISBN 978 3540194880 Horton S B Parker R Gary 1995 On Halin subgraphs and supergraphs 56 1 19 35 doi 10 1016 0166 218X 93 E0131 H MR 1311302 1965 Illinois Journal of Mathematics 9 361 380 MR 0179682 arhiv originalu za 24 lipnya 2018 procitovano 24 lipnya 2018 Chen Guantao Enomoto Hikoe Ozeki Kenta Tsuchiya Shoichi 2015 Plane triangulations without a spanning Halin subgraph counterexamples to the Lovasz Plummer conjecture on Halin graphs SIAM Journal on Discrete Mathematics 29 3 1423 1426 doi 10 1137 140971610 MR 3376776 Skowronska M Syslo M M 1987 Hamiltonian cycles in skirted trees Proceedings of the International Conference on Combinatorial Analysis and its Applications Pokrzywna 1985 Polska Akademia Nauk 19 3 4 599 610 1988 MR 0951375 Lovasz L 1974 On a family of planar bicritical graphs Combinatorics Proc British Combinatorial Conf Univ Coll Wales Aberystwyth 1973 London Cambridge Univ Press s 103 107 London Math Soc Lecture Note Ser No 13 MR 0351915 Demaine Erik D Uehara Ryuhei 2013 Zipper unfolding of domes and prismoids s 43 48 arhiv originalu za 24 lipnya 2018 procitovano 24 lipnya 2018 Posilannya Informacijna sistema pro vklyuchennya klasiv grafiv Weisstein Eric W Halin Graph angl na sajti Wolfram MathWorld Wang Shu Dong Chen Dong Ling Pang Shan Chen 2002 The incidence coloring number of Halin graphs and outerplanar graphs 256 1 2 397 405 doi 10 1016 S0012 365X 01 00302 8 MR 1927561

Дата публікації:
Топ