Гусениця (теорія графів): відмінності між версіями

Інтерактивний перегляд історії

[перевірена версія]

Наступне редагування →

Вилучено вміст Додано вміст

ВізуальнийВікірозмітка

Лінійно

Версія за 15:31, 1 березня 2019

Гусениця або гусеничне дерево — це дерево, в якому всі вершини знаходяться на відстані 1 від центрального шляху.

Графи-гусениці першими почали вивчати в серії статей Харарі та Швенк. Назву запропонував Артур Хоббс^[1]^[2]. Як барвисто писали Харарі та Швенк^[3], «Гусениця — це дерево, яке перетворюється в шлях, якщо видалити кокон з кінцевих вершин»^[1].

Еквівалентні описи

Такі характеристики описують графи-гусениці:

Це дерева, в яких видалення листків разом з ребрами дає шлях^[2]^[4].
Це дерева, в яких існує шлях, що містить всі вершини степеня два і більше.
Це дерева, в яких будь-яка вершина степеня три і більше має не більше двох сусідів, які не є листками.
Це дерева, які не містять в якості підграфів граф, утворений заміною кожного ребра зірки K_1,3 шляхом з двох ребер^[4].
Це зв'язні графи, які можна намалювати, розташувавши вершини на двох паралельних прямих з ребрами, що не перетинаються, а кінцеві вершини кожного ребра розташувавши на різних прямих^[4]^[4]^[5].
Це дерева, квадрат яких є гамільтоновим графом. Під квадратом тут мається на увазі існування циклічної послідовності всіх вершин, при якій кожна пара сусідніх вершин у послідовності знаходяться на відстані один або два. Дерева, що не є гусеницями, такої послідовності не мають. Цикл такого вигляду можна отримати, якщо намалювати гусеницю з вершинами на двох паралельних прямих. Потім нумеруємо вершини на одній прямій в одному напрямку, а на іншій прямій — у зворотному напрямку^[4].
Це дерева, реберні графи яких містять гамільтонів шлях. Такий шлях може бути отриманий шляхом впорядкування ребер на малюнку гусениці з двома прямими. Більш загально, число ребер, які потрібно додати до реберного графа для довільного дерева, щоб він містив гамільтонів шлях (розмір його гамільтонового доповнення●), дорівнює мінімальному числу гусениць, що не перетинаються по ребрах, на які дерево може бути розбите^[6].
Це зв'язні графи з одиничною шириною шляху^[7].
Це зв'язні інтервальні графи без трикутників^[8].

Узагальнення

K-дерево● — це хордальний граф●, що містить рівно n − k максимальних клік, кожна з яких містить k + 1 вершину. В k-дереві, яке саме по собі не є (k + 1)-клікою, кожна максимальна кліка або поділяє граф на дві або більше компонент, або містить (k-)листкову вершину, яка належить тільки одній максимальній кліці. k-шлях — це k-дерево з максимум двома листками, а k-гусениця — це k-дерево, яке можна розбити на k-шляхи і кілька k-листків, кожен з яких суміжний з сепаратором● k-кліки k-шляху. В цій термінології, 1-гусениця — це те ж саме, що й граф-гусениця, а k-гусениці є реберно-максимальними графами зі шириною шляху k^[7].

Краб — це дерево, в якому всі вершини знаходяться на відстані, що не перевершує 2 від центрального шляху^[9]

Перерахування

Гусениці є рідкісним випадком задач перерахування графів, коли відома точна формула — якщо n ≥ 3, число гусениць з n вершинами дорівнює^[1]

2^{n-4}+2^{\lfloor (n-4)/2\rfloor }.

Для n = 1, 2, 3, …число гусениць з n вершинами дорівнює

1, 1, 1, 2, 3, 6, 10, 20, 36, 72, 136, 272, 528, 1056, 2080, 4160, … (послідовність A005418 з Онлайн енциклопедії послідовностей цілих чисел, OEIS).

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

Пошук стягувальної гусениці є NP-повною задачею. Відповідна оптимізаційна задача — задача про мінімальну стягувальну гусеницю (ЗМСГ), в якій задані ціни на ребрах і метою є пошук гусениці, яка мінімізує ціни. Тут ціна гусениці визначається як сума цін її ребер, а кожне ребро має дві ціни, в залежності від того, є воно листком чи внутрішнім ребром. Не існує f(n)-апроксимаційного алгоритму● для ЗМСГ, якщо не виконується P = NP. Тут f(n) — будь-яка функція від n, що обчислюється за поліноміальний час, а n — число вершин графа^[10].

Існує параметризований алгоритм, який знаходить оптимальний розв'язок ЗМСГ у графі з обмеженою шириною дерева^[ru]. Таким чином, завдання про стягувальну гусеницю, так і задача про мінімальну стягувальну гусеницю мають алгоритми лінійного часу, якщо граф зовнішньопланарний, є паралельно-послідовним графом●, або графом Халіна^[10].

Застосування

Гусениці використовуються в хімічній теорії графів● для подання структури молекул бензоїдних вуглеводнів. У цьому поданні молекули утворюють гусениці, в яких кожне ребро відповідає кільцю з 6 атомів вуглецю, а два ребра інцидентні вершині, якщо відповідні бензольні кільця належать послідовності сполучених лінійно кілець. Ель-Базиль (англ. Sherif El-Basil) пише: «Дивно, що майже всі графи, які відіграють важливу роль у тому, що зараз називається „хімічною теорією графів“, пов'язані з графами-гусеницями». У цьому контексті графи-гусениці відомі також як бензоїдні дерева або дерева Гутмана, за роботами Івана Гутмана в цій галузі^[2]^[11]^[12].

Примітки

↑ ^а ^б ^в Harary, Schwenk, 1973, с. 359–365.
↑ ^а ^б ^в El-Basil, 1987, с. 153–174.
↑ Harary, Schwenk, 1973.
↑ ^а ^б ^в ^г ^д Harary, Schwenk, 1971, с. 138–140.
↑ Harary, Schwenk, 1972, с. 203–209.
↑ Raychaudhuri, 1995, с. 299–306.
↑ ^а ^б Proskurowski, Telle, 1999, с. 167–176.
↑ Eckhoff, 1993, с. 117–127.
↑ Weisstein, Eric W. Lobster(англ.) на сайті Wolfram MathWorld.
↑ ^а ^б Khosravani, 2011.
↑ Gutman, 1977, с. 309–315.
↑ El-Basil, 1990, с. 273–289.

Література

Masoud Khosravani. Searching for optimal caterpillars in general and bounded treewidth graphs // Ph.D.. — 2011.
Sherif El-Basil. Applications of caterpillar trees in chemistry and physics // Journal of Mathematical Chemistry. — 1987. — Т. 1, вип. 2. — С. 153–174. — DOI:10.1007/BF01205666.
Ivan Gutman. Topological properties of benzenoid systems // Theoretica Chimica Acta. — 1977. — Т. 45, вип. 4. — С. 309–315. — DOI:10.1007/BF00554539.
Sherif El-Basil. Advances in the Theory of Benzenoid Hydrocarbons. — 1990. — Т. 153. — С. 273–289. — DOI:10.1007/3-540-51505-4_28.
Andrzej Proskurowski, Jan Arne Telle. Classes of graphs with restricted interval models // Discrete Mathematics and Theoretical Computer Science. — 1999. — Т. 3. — С. 167–176.
Arundhati Raychaudhuri. The total interval number of a tree and the Hamiltonian completion number of its line graph // Information Processing Letters. — 1995. — Т. 56, вип. 6. — С. 299–306. — DOI:10.1016/0020-0190(95)00163-8.
Jürgen Eckhoff. Extremal interval graphs // Journal of Graph Theory. — 1993. — Т. 17, вип. 1. — С. 117–127. — DOI:10.1002/jgt.3190170112.
Frank Harary, Allen J. Schwenk. Trees with Hamiltonian square // Mathematika. — 1971. — Т. 18. — С. 138–140. — DOI:10.1112/S0025579300008494.
Frank Harary, Allen J. Schwenk. A new crossing number for bipartite graphs // Utilitas Math.. — 1972. — Т. 1. — С. 203–209.
Frank Harary, Allen J. Schwenk. The number of caterpillars // Discrete Mathematics. — 1973. — Т. 6, вип. 4. — С. 359–365. — DOI:10.1016/0012-365x(73)90067-8.

Посилання

Weisstein, Eric W. Caterpillar(англ.) на сайті Wolfram MathWorld.

[FOOTNOTEHarary,_Schwenk1973359–365-1] а ^б ^в Harary, Schwenk, 1973, с. 359–365.

[FOOTNOTEEl-Basil1987153–174-2] а ^б ^в El-Basil, 1987, с. 153–174.

[FOOTNOTEHarary,_Schwenk1973-3] Harary, Schwenk, 1973.

[FOOTNOTEHarary,_Schwenk1971138–140-4] а ^б ^в ^г ^д Harary, Schwenk, 1971, с. 138–140.

[FOOTNOTEHarary,_Schwenk1972203–209-5] Harary, Schwenk, 1972, с. 203–209.

[FOOTNOTERaychaudhuri1995299–306-6] Raychaudhuri, 1995, с. 299–306.

[FOOTNOTEProskurowski,_Telle1999167–176-7] а ^б Proskurowski, Telle, 1999, с. 167–176.

[FOOTNOTEEckhoff1993117–127-8] Eckhoff, 1993, с. 117–127.

[9] Weisstein, Eric W. Lobster(англ.) на сайті Wolfram MathWorld.

[FOOTNOTEKhosravani2011-10] а ^б Khosravani, 2011.

[FOOTNOTEGutman1977309–315-11] Gutman, 1977, с. 309–315.

[FOOTNOTEEl-Basil1990273–289-12] El-Basil, 1990, с. 273–289.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

@@ Рядок 1: / Рядок 1: @@
 [[Файл:Caterpillar_tree.svg|міні|300x300пкс|Гусениця]]
-'''Гусениця''' або '''гусеничне дерево''' — це [[Дерево (теорія графів)|дерево]], в якому всі вершини знаходяться на відстані 1 від центрального шляху.
+'''Гусениця''' або '''гусеничне дерево'''&nbsp;— це [[Дерево (теорія графів)|дерево]], в якому всі вершини знаходяться на відстані 1 від центрального шляху.
-Графи-гусениці першими почали вивчати в серії статей Харарі та Швенке. Назву запропонував Артур Хоббс{{sfn|Harary, Schwenk|1973|с=359–365}}{{sfn|El-Basil|1987|с=153–174}}. Як барвисто писали [[Френк Харарі|Харарі]] та Швенке{{sfn|Harary, Schwenk|1973}}, «Гусениця — це дерево, яке перетворюється в шлях, якщо видалити кокон з кінцевих вершин»{{sfn|Harary, Schwenk|1973|с=359–365}}.
+Графи-гусениці першими почали вивчати в серії статей [[Френк Харарі|Харарі]] та [[Аллен Швенк|Швенк]]. Назву запропонував Артур Хоббс{{sfn|Harary, Schwenk|1973|с=359–365}}{{sfn|El-Basil|1987|с=153–174}}. Як барвисто писали Харарі та Швенк{{sfn|Harary, Schwenk|1973}}, «Гусениця&nbsp;— це дерево, яке перетворюється в шлях, якщо видалити кокон з кінцевих вершин»{{sfn|Harary, Schwenk|1973|с=359–365}}.
 == Еквівалентні описи ==
@@ Рядок 13: / Рядок 12: @@
 * Це дерева, які не містять в якості підграфів граф, утворений заміною кожного ребра [[Зірка (теорія графів)|зірки]] ''K''<sub>1,3</sub> шляхом з двох ребер{{sfn|Harary, Schwenk|1971|с=138–140}}.
 * Це зв'язні графи, які можна [[Візуалізація графів|намалювати]], розташувавши вершини на двох паралельних прямих з ребрами, що не перетинаються, а кінцеві вершини кожного ребра розташувавши на різних прямих{{sfn|Harary, Schwenk|1971|с=138–140}}{{sfn|Harary, Schwenk|1971|с=138–140}}{{sfn|Harary, Schwenk|1972|с=203–209}}.
-* Це дерева, квадрат яких є [[Гамільтонів граф|гамільтоновим графом]]. Під квадратом тут мається на увазі існування циклічної послідовності всіх вершин, при якій кожна пара сусідніх вершин у послідовності знаходяться на відстані один або два. Дерева, що не є гусеницями, такої послідовності не мають. Цикл такого вигляду можна отримати, якщо намалювати гусеницю з вершинами на двох паралельних прямих. Потім нумеруємо вершини на одній прямій в одному напрямку, а на іншій прямій — у зворотному напрямку{{sfn|Harary, Schwenk|1971|с=138–140}}.
+* Це дерева, квадрат яких є [[Гамільтонів граф|гамільтоновим графом]]. Під квадратом тут мається на увазі існування циклічної послідовності всіх вершин, при якій кожна пара сусідніх вершин у послідовності знаходяться на відстані один або два. Дерева, що не є гусеницями, такої послідовності не мають. Цикл такого вигляду можна отримати, якщо намалювати гусеницю з вершинами на двох паралельних прямих. Потім нумеруємо вершини на одній прямій в одному напрямку, а на іншій прямій&nbsp;— у зворотному напрямку{{sfn|Harary, Schwenk|1971|с=138–140}}.
-* Це дерева, [[Реберний граф|реберні графи]] яких містять [[Гамільтонів граф|гамільтонів шлях]]. Такий шлях може бути отриманий шляхом впорядкування ребер на малюнку гусениці з двома прямими. Більш загально, число ребер, які потрібно додати до реберного графа для довільного дерева, щоб він містив гамільтонів шлях (розмір його гамільтонового поповнення[en]), дорівнює мінімальному числу гусениць, що не перетинаються по ребрах, на які дерево може бути розбите{{sfn|Raychaudhuri|1995|с=299–306}}.
+* Це дерева, [[Реберний граф|реберні графи]] яких містять [[Гамільтонів граф|гамільтонів шлях]]. Такий шлях може бути отриманий шляхом впорядкування ребер на малюнку гусениці з двома прямими. Більш загально, число ребер, які потрібно додати до реберного графа для довільного дерева, щоб він містив гамільтонів шлях (розмір його {{нп|Гамільтонове доповнення|гамільтонового доповнення|ru|Гамильтоново дополнение}}), дорівнює мінімальному числу гусениць, що не перетинаються по ребрах, на які дерево може бути розбите{{sfn|Raychaudhuri|1995|с=299–306}}.
 * Це зв'язні графи з одиничною [[Ширина шляху графу|шириною шляху]]{{sfn|Proskurowski, Telle|1999|с=167–176}}.
 * Це зв'язні [[Інтервальний граф|інтервальні графи]] [[Граф без трикутників|без трикутників]]{{sfn|Eckhoff|1993|с=117–127}}.
 == Узагальнення ==
-K-дерево[en] — це [[хордальный граф]], що містить рівно {{Nobr|''n'' &minus; ''k''}} [[Кліка (теорія графів)|максимальних клік]], кожна з яких містить {{Nobr|''k'' + 1}} вершину. В ''k''-дереві, яке саме по собі не є {{Nobr|(''k'' + 1)-клікою}}, кожна максимальна кліка або поділяє граф на дві або більше компонент, або містить (''k''-)листкову вершину, яка належить тільки одній максимальній кліці. ''k''-шлях — це ''k''-дерево з максимум двома листками, а ''k''-гусениця — це ''k''-дерево, яке можна розбити на ''k''-шляхи і кілька ''k''-листків, кожен з яких суміжний з [[Вершинный сепаратор (теория графов)|сепаратором]] ''k''-кліки ''k''-шляху. В цій термінології, 1-гусениця — це те ж саме, що й граф-гусениця, а ''k''-гусениці є реберно-максимальними графами зі [[Ширина шляху графу|шириною шляху]] ''k''{{sfn|Proskurowski, Telle|1999|с=167–176}}.
+{{нп|K-дерево|||K-tree}}&nbsp;— це {{нп|хордальний граф|хордальний граф|ru|Хордальный граф}}, що містить рівно {{Nobr|''n'' &minus; ''k''}} [[Кліка (теорія графів)|максимальних клік]], кожна з яких містить {{Nobr|''k'' + 1}} вершину. В ''k''-дереві, яке саме по собі не є {{Nobr|(''k'' + 1)-клікою}}, кожна максимальна кліка або поділяє граф на дві або більше компонент, або містить (''k''-)листкову вершину, яка належить тільки одній максимальній кліці. ''k''-шлях&nbsp;— це ''k''-дерево з максимум двома листками, а ''k''-гусениця&nbsp;— це ''k''-дерево, яке можна розбити на ''k''-шляхи і кілька ''k''-листків, кожен з яких суміжний з {{нп|Вершинний сепаратор (теорія графів)|сепаратором|ru|Вершинный сепаратор (теория графов)}} ''k''-кліки ''k''-шляху. В цій термінології, 1-гусениця&nbsp;— це те ж саме, що й граф-гусениця, а ''k''-гусениці є реберно-максимальними графами зі [[Ширина шляху графу|шириною шляху]] ''k''{{sfn|Proskurowski, Telle|1999|с=167–176}}.
-'''Краб''' — це [[Дерево (теорія графів)|дерево]], в якому всі вершини знаходяться на відстані, що не перевершує 2 від центрального [[Шлях (граф)|шляху]]<ref>{{MathWorld|urlname=Lobster|title=Lobster}}</ref>
+'''Краб'''&nbsp;— це [[Дерево (теорія графів)|дерево]], в якому всі вершини знаходяться на відстані, що не перевершує 2 від центрального [[Шлях (теорія графів)|шляху]]<ref>{{MathWorld|urlname=Lobster|title=Lobster}}</ref>
 == Перерахування ==
-Гусениці є рідкісним випадком задач [[Перерахування графів|перерахування графів]], коли відома точна формула — якщо ''n''&nbsp;≥&nbsp;3, число гусениць з ''n'' вершинами дорівнює{{sfn|Harary, Schwenk|1973|с=359–365}}
+Гусениці є рідкісним випадком задач [[Перерахування графів|перерахування графів]], коли відома точна формула&nbsp;— якщо ''n''&nbsp;≥&nbsp;3, число гусениць з ''n'' вершинами дорівнює{{sfn|Harary, Schwenk|1973|с=359–365}}
 : <math>2^{n-4}+2^{\lfloor (n-4)/2\rfloor}.</math>
-Для ''n'' = 1, 2, 3, ...число гусениць з ''n'' вершинами дорівнює
+Для ''n'' = 1, 2, 3, …число гусениць з ''n'' вершинами дорівнює
-: 1, 1, 1, 2, 3, 6, 10, 20, 36, 72, 136, 272, 528, 1056, 2080, 4160, ... ({{OEIS|A005418}}).
+: 1, 1, 1, 2, 3, 6, 10, 20, 36, 72, 136, 272, 528, 1056, 2080, 4160, … ({{OEIS|A005418}}).
 == Обчислювальна складність ==
-Пошук стягувальної гусениці є [[NP-повна задача|NP-повною задачею]]. Відповідна оптимізаційна задача — задача про мінімальну стягувальну гусеницю (ЗМСГ), в якій задані ціни на ребрах і метою є пошук гусениці, яка мінімізує ціни. Тут ціна гусениці визначається як сума цін її ребер, а кожне ребро має дві ціни, в залежності від того, є воно листком чи внутрішнім ребром. Не існує f(n)-[[Аппроксимационный алгоритм|аппроксимационного алгоритму]] для ЗМСГ, якщо не виконується [[Рівність класів P і NP|P = NP]]. Тут f(n) — будь-яка функція від n, що обчислюється за поліноміальний час, а n — число вершин графа{{sfn|Khosravani|2011}}.
+Пошук стягувальної гусениці є [[NP-повна задача|NP-повною задачею]]. Відповідна оптимізаційна задача&nbsp;— задача про мінімальну стягувальну гусеницю (ЗМСГ), в якій задані ціни на ребрах і метою є пошук гусениці, яка мінімізує ціни. Тут ціна гусениці визначається як сума цін її ребер, а кожне ребро має дві ціни, в залежності від того, є воно листком чи внутрішнім ребром. Не існує f(n)-{{нп|Апроксимаційний алгоритм|апроксимаційного алгоритму|ru|Аппроксимационный алгоритм}} для ЗМСГ, якщо не виконується [[Рівність класів P і NP|P = NP]]. Тут f(n)&nbsp;— будь-яка функція від n, що обчислюється за поліноміальний час, а n&nbsp;— число вершин графа{{sfn|Khosravani|2011}}.
-Існує параметризований алгоритм, який знаходить оптимальний розв’язок ЗМСГ у графі з обмеженою [[Древесная ширина (теория графов)|деревною шириною]]. Таким чином, завдання про стягувальну гусеницю, так і задача про мінімальну стягувальну гусеницю мають алгоритми лінійного часу, якщо граф [[Внешнепланарный граф|зовнішньопланарний]], є [[Параллельно-последовательный граф|паралельно-послідовним графом]], або [[Граф Халіна|графом Халіна]]{{sfn|Khosravani|2011}}.
+Існує параметризований алгоритм, який знаходить оптимальний розв'язок ЗМСГ у графі з обмеженою {{нп|Ширина дерева (теорія графів)|шириною дерева|ru|Древесная ширина (теория графов)}}. Таким чином, завдання про стягувальну гусеницю, так і задача про мінімальну стягувальну гусеницю мають алгоритми лінійного часу, якщо граф [[Внешнепланарный граф|зовнішньопланарний]], є {{нп|Паралельно-послідовний граф|паралельно-послідовним графом|ru|Параллельно-последовательный граф}}, або [[Граф Халіна|графом Халіна]]{{sfn|Khosravani|2011}}.
+== Застосування ==
-== Додатки ==
-Гусениці використовуються в хімічній теорії графів[en] для подання структури молекул бензоїдних [[Вуглеводні|вуглеводнів]]. У цьому поданні молекули утворюють гусениці, в яких кожне ребро відповідає кільцю з 6 атомів вуглецю, а два ребра инцидентні вершині, якщо відповідні бензольні кільця належать послідовності сполучених лінійно кілець. Ель-Базиль пише: «Дивно, що майже всі графи, які відіграють важливу роль у тому, що зараз називається «хімічною теорією графів», пов'язані з графами-гусеницями». У цьому контексті графи-гусениці відомі також як '''бензоїдні дерева''' або '''дерева Гутмана''', за роботами Івана Гутмана в цій галузі{{sfn|El-Basil|1987|с=153–174}}{{sfn|Gutman|1977|с=309–315}}{{sfn|El-Basil|1990|с=273–289}}.
+Гусениці використовуються в {{нп|Хімічна теорія графів|хімічній теорії графів||Chemical graph theory}} для подання структури молекул бензоїдних [[Вуглеводні|вуглеводнів]]. У цьому поданні молекули утворюють гусениці, в яких кожне ребро відповідає кільцю з 6 атомів вуглецю, а два ребра інцидентні вершині, якщо відповідні бензольні кільця належать послідовності сполучених лінійно кілець. [[Шериф Ель-Базиль|Ель-Базиль]] ({{lang-en|Sherif El-Basil}}) пише: «Дивно, що майже всі графи, які відіграють важливу роль у тому, що зараз називається „хімічною теорією графів“, пов'язані з графами-гусеницями». У цьому контексті графи-гусениці відомі також як '''бензоїдні дерева''' або '''дерева Гутмана''', за роботами Івана Гутмана в цій галузі{{sfn|El-Basil|1987|с=153–174}}{{sfn|Gutman|1977|с=309–315}}{{sfn|El-Basil|1990|с=273–289}}.
 == Примітки ==
+{{примітки|2}}
 == Література ==
+{{refbegin|colwidth=30em}}
+* {{стаття|видання=Ph.D.|автор=Masoud Khosravani|назва=Searching for optimal caterpillars in general and bounded treewidth graphs|издательство=University of Auckland|рік=2011|url=https://researchspace.auckland.ac.nz/handle/2292/8360?show=full|ref=Khosravani}}
+* {{стаття|автор=Sherif El-Basil|doi=10.1007/BF01205666|випуск=2|видання=Journal of Mathematical Chemistry|сторінки=153–174|назва=Applications of caterpillar trees in chemistry and physics|том=1|рік=1987|ref=El-Basil}}
+* {{стаття|автор=Ivan Gutman|doi=10.1007/BF00554539|випуск=4|видання=Theoretica Chimica Acta|сторінки=309–315|назва=Topological properties of benzenoid systems|том=45|рік=1977|ref=Gutman}}
+* {{книга|автор=Sherif El-Basil|вклад=Caterpillar (Gutman) trees in chemical graph theory|doi=10.1007/3-540-51505-4_28|ответственный=I. Gutman, S. J. Cyvin|сторінки=273–289|серия=Topics in Current Chemistry|назва=Advances in the Theory of Benzenoid Hydrocarbons|том=153|рік=1990|ref=El-Basil}}
+* {{стаття|автор=Andrzej Proskurowski, Jan Arne Telle|видання=Discrete Mathematics and Theoretical Computer Science|сторінки=167–176|назва=Classes of graphs with restricted interval models|url=http://www.emis.ams.org/journals/DMTCS/volumes/abstracts/pdfpapers/dm030404.pdf|том=3|рік=1999|ref=Proskurowski, Telle}}
+* {{стаття|автор=Arundhati Raychaudhuri|doi=10.1016/0020-0190(95)00163-8|випуск=6|видання=Information Processing Letters|сторінки=299–306|назва=The total interval number of a tree and the Hamiltonian completion number of its line graph|том=56|рік=1995|ref=Raychaudhuri}}
+* {{стаття|автор=Jürgen Eckhoff|doi=10.1002/jgt.3190170112|випуск=1|видання=Journal of Graph Theory|сторінки=117–127|назва=Extremal interval graphs|том=17|рік=1993|ref=Eckhoff}}
+* {{стаття|автор=[[Френк Харарі|Frank Harary]], Allen J. Schwenk|doi=10.1112/S0025579300008494|видання=Mathematika|сторінки=138–140|назва=Trees with Hamiltonian square|том=18|рік=1971|ref=Harary, Schwenk}}
+* {{стаття|автор=Frank Harary, Allen J. Schwenk|видання=Utilitas Math.|сторінки=203–209|назва=A new crossing number for bipartite graphs|том=1|рік=1972|ref=Harary, Schwenk}}
+* {{стаття|автор=Frank Harary, Allen J. Schwenk|випуск=4|видання=Discrete Mathematics|сторінки=359–365|назва=The number of caterpillars|том=6|рік=1973|doi=10.1016/0012-365x(73)90067-8|ref=Harary, Schwenk}}
+{{refend}}
 == Посилання ==
+* {{mathworld|urlname=Caterpillar|title=Caterpillar}}
 [[Категорія:Дерева (теорія графів)]]
-[[Категорія:Сторінки із неперевіреними перекладами]]