У меня есть график G , который состоит только из звездных графиков.Звездный граф состоит из одного центрального узла, имеющего ребра для каждого другого узла в нем.Пусть H 1 , H 2 ,…, H n - различные звездные диаграммы разных размеров, которые присутствуют в G.Мы называем множество всех узлов, которые являются центрами в любом звездном графе R .
Теперь предположим, что эти звездные графы строят ребра для других звездных графов, так что между любыми узлами в ребре не возникает ни одного ребра R .Тогда, сколько существует ребер в максимуме между узлами в R и узлами, которые не находятся в R , если график должен оставаться плоским?
Я хочуверхняя граница числа таких ребер.Одна верхняя граница, которую я имею в виду: рассматривайте их как двудольный планарный граф, где R - один набор вершин, а остальные вершины образуют другой набор A .Нас интересуют ребра между этими наборами ( R и A ).Поскольку это плоское двудольное, число таких ребер ограничено двойным числом узлов в G .
Я чувствую, что есть лучшая граница, возможно, в два раза больше узлов в A плюс количество узлов в R .
Если вы можете опровергнуть мою интуицию, тогда это тоже будет хорошо.Надеюсь, что некоторые из вас могут прийти с хорошей оценкой вместе с некоторыми соответствующими аргументами.