Сферичность (теория графов)

В теории графов сферичность , графа определяемый — это инвариант графа, как наименьшее измерение евклидова пространства необходимое для реализации графа как графа пересечения единичных сфер . Сферичность графа является обобщением инвариантов коробчатости и кубичности , определенных Ф. С. Робертсом в конце 1960-х годов. ^[1]^[2] Понятие сферичности было впервые введено Хироши Маэхарой в начале 1980-х годов. ^[3]

Определение

Позволять $G$ быть графиком. Тогда сферичность $G$ , обозначенный $\operatorname {sph} (G)$ , является наименьшим целым числом $n$ такой, что $G$ может быть реализован как граф пересечений единичных сфер в $n$ -мерное евклидово пространство $\mathbb {R} ^{n}$ . ^[4]

Сферичность также можно определить на языке пространственных графов следующим образом. Для конечного набора точек в некотором $n$ В -мерном евклидовом пространстве пространственный граф строится путем соединения пар точек отрезком прямой , когда их евклидово расстояние меньше некоторой заданной константы. Тогда сферичность графа $G$ это минимум $n$ такой, что $G$ изоморфен в пространственному графу $\mathbb {R} ^{n}$ . ^[3]

Графы сферичности 1 известны как интервальные графы или графы безразличия . Графы сферичности 2 известны как графы единичного диска .

Границы

Сферичность некоторых классов графов можно вычислить точно. Следующие сферичности были даны Маэхарой на странице 56 его оригинальной статьи по этой теме.


График	Описание	Сферичность	Примечания
$K_{1}$	Полный график	0
$K_{n}$	Полный график	1	$n>1$
$P_{n}$	Граф пути	1	$n>1$
$C_{n}$	Схема цепи	2	$n>3$
$K_{m(2)}$	Полный m-частный граф на m наборах размера 2	2	$m>1$

Наиболее общая известная верхняя оценка сферичности состоит в следующем. Если считать, что граф неполный , то $\operatorname {sph} (G)\leq |G|-\omega (G)$ где $\omega (G)$ это кликовое число $G$ и $|G|$ обозначает количество вершин $G.$ ^[3]

Ссылки

^ Робертс, FS (1969). О коробочности и кубичности графа. В WT Tutte (ред.), «Недавний прогресс в комбинаторике» (стр. 301–310). Сан-Диего, Калифорния: Academic Press. ISBN 978-0-12-705150-5
^ Фишберн, Питер С. (1 декабря 1983 г.). «О сферичности и кубичности графов» . Журнал комбинаторной теории, серия B. 35 (3): 309–318. дои : 10.1016/0095-8956(83)90057-6 . ISSN 0095-8956 .
^ Jump up to: ^а ^б ^с Маэхара, Хироши (1 января 1984 г.). «Пространственные графы и сферичность» . Дискретная прикладная математика . 7 (1): 55–64. дои : 10.1016/0166-218X(84)90113-6 . ISSN 0166-218X .
^ Маэхара, Хироши (1 марта 1986 г.). «О сферичности графов полуправильных многогранников» . Дискретная математика . 58 (3): 311–315. дои : 10.1016/0012-365X(86)90150-0 . ISSN 0012-365X .

[1] Робертс, FS (1969). О коробочности и кубичности графа. В WT Tutte (ред.), «Недавний прогресс в комбинаторике» (стр. 301–310). Сан-Диего, Калифорния: Academic Press. ISBN 978-0-12-705150-5

[2] Фишберн, Питер С. (1 декабря 1983 г.). «О сферичности и кубичности графов» . Журнал комбинаторной теории, серия B. 35 (3): 309–318. дои : 10.1016/0095-8956(83)90057-6 . ISSN 0095-8956 .

[:0-3] Jump up to: ^а ^б ^с Маэхара, Хироши (1 января 1984 г.). «Пространственные графы и сферичность» . Дискретная прикладная математика . 7 (1): 55–64. дои : 10.1016/0166-218X(84)90113-6 . ISSN 0166-218X .

[4] Маэхара, Хироши (1 марта 1986 г.). «О сферичности графов полуправильных многогранников» . Дискретная математика . 58 (3): 311–315. дои : 10.1016/0012-365X(86)90150-0 . ISSN 0012-365X .

[1]

[2]

[3]

[4]