|
Дискретная математика, 1991, том 3, выпуск 4, страницы 91–104
(Mi dm825)
|
|
|
|
О циклических свойствах некоторых гамильтоновых графов
А. С. Асратян, Г. В. Саркисян
Аннотация:
Исследуется множество циклов связного графа $G=(V,X)$ с $|V|\geqslant5$, в котором
$$
d(x)+d(y)\geqslant|N(x)\cup N(y)\cup N(z)|
$$
для каждой тройки вершин $x$, $y$, $z$ с $d(x,y)=2$ и $z\in N(x)\cap N(y)$, где $d(x,y)$ – расстояние между вершинами $x$, $y$, а для каждого $u\in V$, $N(u)$ – подмножество вершин из $V$, смежных с $u$. Показано, что если $G$ не совпадает с полным двудольным графом $K_{m,m}$ при $m\geqslant2$, то в $G$ существует цикл любой длины $n$ $(3\leqslant n\leqslant|V|)$. Более того, показано, что для каждой
вершины $x$ в таком графе $G$ существует такой набор простых циклов $C_4,C_5,\dots C_p$ $(p=|V|)$ с длинами $4,5,\dots,p$, $x\in C_4$ для каждого $n$ $4\leqslant n<|V|$, выполнено $V(C_n)\subset V(C_{n+1})$ (или $V(C_n)\subset V(C_{n+2})$) и $V(C_{n+1})\subset V(C_{n+2})$, где $V(C_i)$ – множество вершин цикла $C_i$ $(i=4,\dots,p)$.
Статья поступила: 10.09.1990
Образец цитирования:
А. С. Асратян, Г. В. Саркисян, “О циклических свойствах некоторых гамильтоновых графов”, Дискрет. матем., 3:4 (1991), 91–104; Discrete Math. Appl., 2:6 (1992), 623–637
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/dm825 https://www.mathnet.ru/rus/dm/v3/i4/p91
|
|