Английская Википедия:(a, b)-decomposition

Материал из Онлайн справочника
Версия от 00:43, 18 декабря 2023; EducationBot (обсуждение | вклад) (Новая страница: «{{Английская Википедия/Панель перехода}} {{DISPLAYTITLE:(''a'', ''b'')-decomposition}} In graph theory, the '''(''a'', ''b'')-decomposition''' of an undirected graph is a partition of its edges into ''a'' + 1 sets, each one of them inducing a forest, except one which induces a graph with maximum degree ''b''. If this graph is also a forest, then we call this a ''' F(''a'', ''b'')-...»)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигацииПерейти к поиску

In graph theory, the (a, b)-decomposition of an undirected graph is a partition of its edges into a + 1 sets, each one of them inducing a forest, except one which induces a graph with maximum degree b. If this graph is also a forest, then we call this a F(a, b)-decomposition.

A graph with arboricity a is (a, 0)-decomposable. Every (a, 0)-decomposition or (a, 1)-decomposition is a F(a, 0)-decomposition or a F(a, 1)-decomposition respectively.

Graph classes

  • Every planar graph is F(2, 4)-decomposable.[1]
  • Every planar graph <math>G</math> with girth at least <math>g</math> is
    • F(2, 0)-decomposable if <math>g \ge 4</math>.[2]
    • (1, 4)-decomposable if <math>g \ge 5</math>.[3]
    • F(1, 2)-decomposable if <math>g \ge 6</math>.[4]
    • F(1, 1)-decomposable if <math>g \ge 8</math>,[5] or if every cycle of <math>G</math> is either a triangle or a cycle with at least 8 edges not belonging to a triangle.[6]
    • (1, 5)-decomposable if <math>G</math> has no 4-cycles.[7]
  • Every outerplanar graph is F(2, 0)-decomposable[2] and (1, 3)-decomposable.[8]

Notes

Шаблон:Reflist

References (chronological order)

Шаблон:Refbegin

Шаблон:Refend

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  1. ↑ Шаблон:Harvtxt, conjectured by Шаблон:Harvtxt. Improving results by Шаблон:Harvtxt then Шаблон:Harvtxt.
  2. ↑ Перейти обратно: 2,0 2,1 Implied by Шаблон:Harvtxt.
  3. ↑ Шаблон:Harvtxt
  4. ↑ Implied by Шаблон:Harvtxt, improving results by Шаблон:Harvtxt, then Шаблон:Harvtxt.
  5. ↑ Independently proved by Шаблон:Harvtxt and implied by Шаблон:Harvtxt, improving results by Шаблон:Harvtxt for girth 11, then Шаблон:Harvtxt for girth 10 and Шаблон:Harvtxt for girth 9.
  6. ↑ Шаблон:Harvtxt, even if not explicitly stated.
  7. ↑ Шаблон:Harvtxt, improving results by Шаблон:Harvtxt, then Шаблон:Harvtxt.
  8. ↑ Proved without explicit reference by Шаблон:Harvtxt.
Источник — http://wikihandbk.com/ruwiki/index.php?title=Английская_Википедия:(a,_b)-decomposition&oldid=12481008