Buletinul Academiei de Ştiinţe a Republicii Moldova. Matematica
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив
Импакт-фактор

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

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



Bul. Acad. Ştiinţe Repub. Mold. Mat.:
Год:
Том:
Выпуск:
Страница:
Найти






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


Buletinul Academiei de Ştiinţe a Republicii Moldova. Matematica, 2014, номер 3, страницы 3–12 (Mi basm374)  

Estimates for the number of vertices with an interval spectrum in proper edge colorings of some graphs

R. R. Kamalian

Institute for Informatics and Automation Problems, National Academy of Sciences of RA, 0014 Yerevan, Republic of Armenia
Список литературы:
Аннотация: For an undirected, simple, finite, connected graph $G$, we denote by $V(G)$ and $E(G)$ the sets of its vertices and edges, respectively. A function $\varphi\colon E(G)\to\{1,2,\dots,t\}$ is called a proper edge $t$-coloring of a graph $G$ if all colors are used and no two adjacent edges receive the same color. An arbitrary nonempty subset of consecutive integers is called an interval. The set of all proper edge $t$-colorings of $G$ is denoted by $\alpha(G,t)$. The minimum value of $t$ for which there exists a proper edge $t$-coloring of a graph $G$ is denoted by $\chi'(G)$. Let
$$ \alpha(G)\equiv\bigcup_{t=\chi'(G)}^{|E(G)|}\alpha(G,t). $$
If $G$ is a graph, $\varphi\in\alpha(G)$, $x\in V(G)$, then the set of colors of edges of $G$ incident with $x$ is called a spectrum of the vertex $x$ in the coloring $\varphi$ of the graph $G$ and is denoted by $S_G(x,\varphi)$. If $\varphi\in\alpha(G)$ and $x\in V(G)$, then we say that $\varphi$ is interval (persistent-interval) for $x$ if $S_G(x,\varphi)$ is an interval (an interval with 1 as its minimum element). For an arbitrary graph $G$ and any $\varphi\in\alpha(G)$, we denote by $f_{G,i}(\varphi)(f_{G,pi}(\varphi))$ the number of vertices of the graph $G$ for which $\varphi$ is interval (persistent-interval). For any graph $G$, let us set
$$ \eta_i(G)\equiv\max_{\varphi\in\alpha(G)}f_{G,i}(\varphi),\quad\eta_{pi}(G)\equiv\max_{\varphi\in\alpha(G)}f_{G,pi}(\varphi). $$
For graphs $G$ from some classes of graphs, we obtain lower bounds for the parameters $\eta_i(G)$ and $\eta_{pi}(G)$.
Ключевые слова и фразы: proper edge coloring, interval spectrum.
Поступила в редакцию: 30.04.2013
Тип публикации: Статья
MSC: 05C15
Язык публикации: английский
Образец цитирования: R. R. Kamalian, “Estimates for the number of vertices with an interval spectrum in proper edge colorings of some graphs”, Bul. Acad. Ştiinţe Repub. Mold. Mat., 2014, no. 3, 3–12
Цитирование в формате AMSBIB
\RBibitem{Kam14}
\by R.~R.~Kamalian
\paper Estimates for the number of vertices with an interval spectrum in proper edge colorings of some graphs
\jour Bul. Acad. \c Stiin\c te Repub. Mold. Mat.
\yr 2014
\issue 3
\pages 3--12
\mathnet{http://mi.mathnet.ru/basm374}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/basm374
  • https://www.mathnet.ru/rus/basm/y2014/i3/p3
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Buletinul Academiei de Ştiinţe a Republicii Moldova. Matematica
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2024