Кубичность

В теории графов кубичность — это инвариант графа, определяемый как наименьшее измерение, такое, что граф может быть реализован как граф пересечений единичных кубов в евклидовом пространстве . Кубичность была введена Фредом С. Робертсом в 1969 году вместе с соответствующим инвариантом, называемым коробчатостью , который учитывает наименьшее измерение, необходимое для представления графа как графа пересечения прямоугольников , параллельных осям , в евклидовом пространстве. ^[1]

Определение

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

Кубичность графа тесно связана с кубичностью графа, обозначаемой $\operatorname {box} (G)$ . Определение квадратичности по сути такое же, как и кубичность, за исключением использования прямоугольников, параллельных осям, вместо кубов. Поскольку куб является частным случаем прямоугольника, кубичность графа всегда является верхней границей квадратичности графа. В обратном направлении можно показать, что для любого графа $G$ на $m$ вершины, неравенство $\operatorname {cub} (G)\leq \lceil \log _{2}n\rceil \operatorname {box} (G)$ , где $\lceil x\rceil$ — функция потолка , т. е. наименьшее целое число, большее или равное $x$ . ^[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 .
^ Сунил Чандран, Л.; Ашик Мэтью, К. (28 апреля 2009 г.). «Верхняя граница кубичности с точки зрения коробочности» . Дискретная математика . 309 (8): 2571–2574. arXiv : math/0605486 . дои : 10.1016/j.disc.2008.04.011 . ISSN 0012-365X . S2CID 7837544 .

[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 .

[3] Сунил Чандран, Л.; Ашик Мэтью, К. (28 апреля 2009 г.). «Верхняя граница кубичности с точки зрения коробочности» . Дискретная математика . 309 (8): 2571–2574. arXiv : math/0605486 . дои : 10.1016/j.disc.2008.04.011 . ISSN 0012-365X . S2CID 7837544 .

[1]

[2]

[3]