RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Тр. Ин-та матем.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Тр. Ин-та матем., 2010, том 18, номер 2, страницы 79–86 (Mi timb19)  

Профиль короны $G\wedge H$, где $G$ — граф Халина, древесной основой которого является гусеница

В. В. Лепин, С. А. Тихон

Институт математики НАН Беларуси

Аннотация: Пусть $G=(V,E)$ — неориентированный граф на $n$ вершинах. Линейным размещением графа $G$ называется взаимно однозначное отображение $f\colon V\to\{1,2,…,n\}$. В задаче о профиле графа $G$ требуется найти его профиль:
$$ p(G)=\min_f\sum_{v\in V}\max_{u\in N[v]}(f(v)-f(u)), $$
где $N[v]=\{v\}\cup\{u\in V:\{v,u\}\in E\}$ и минимум берется по всевозможным линейным размещениям графа $G$. Показано, что если $G$ — граф Халина, древесной основой которого является гусеница, то $p(G)=3(n-2)$ и профиль короны двух графов
$$ p(G\wedge H)=3(n-2)+np(H)+(3n-6)m, $$
где $n=|V(G)|$, $m=|V(H)|$.

Полный текст: PDF файл (267 kB)
Список литературы: PDF файл   HTML файл

Реферативные базы данных:
Тип публикации: Статья
УДК: 519.1
Поступила в редакцию: 30.05.2010

Образец цитирования: В. В. Лепин, С. А. Тихон, “Профиль короны $G\wedge H$, где $G$ — граф Халина, древесной основой которого является гусеница”, Тр. Ин-та матем., 18:2 (2010), 79–86

Цитирование в формате AMSBIB
\RBibitem{LepTsi10}
\by В.~В.~Лепин, С.~А.~Тихон
\paper Профиль короны $G\wedge H$, где $G$~--- граф Халина, древесной основой которого является гусеница
\jour Тр. Ин-та матем.
\yr 2010
\vol 18
\issue 2
\pages 79--86
\mathnet{http://mi.mathnet.ru/timb19}
\zmath{https://zbmath.org/?q=an:05863492}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/timb19
  • http://mi.mathnet.ru/rus/timb/v18/i2/p79

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Труды Института математики
    Просмотров:
    Эта страница:162
    Полный текст:116
    Литература:19
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020