Скажем, семейство графов имеет длинные индуцированные пути, если существует константа ϵ > 0 такая, что каждый граф G в F содержит индуцированный путь на | V ( G ) | ϵ вершины. Меня интересуют свойства семейств графов, которые обеспечивают существование длинных индуцированных путей. В частности, я в настоящее время задаюсь вопросом, имеют ли расширители постоянной степени длинные индуцированные пути. Вот что я знаю.
- Случайные графы с постоянной средней степенью (в модели Эрдеша – Реньи) имеют длинные (даже линейного размера) индуцированные пути с высокой вероятностью; см. например статью Суена .
- Графы расширителей уникальных соседей (согласно определению Алона и Копальбо ) имеют большие индуцированные деревья . На самом деле любое максимальное индуцированное дерево велико в таких графах.
Учитывая эти два факта, я ожидал бы, что расширители с уклоном степени имеют длинные индуцированные пути. Однако я не смог найти никаких конкретных результатов. Любые идеи очень ценятся.
источник