Let G be a graph on n vertices and minimum degree ± with degree sequence ± = d1 · d2 · ::: · dn. The minimum degree sum of two nonadjacent vertices in G is denoted by ¾2. Let c be the circumference - the order (the number of vertices) of a longest cycle, and p be the order of a longest path in G. In 1952, Dirac proved: (1) if G is a 2-connected graph, then c ¸ minfn; 2d1g; (2) every graph with d1 ¸ n 2 is hamiltonian. Recently, these results were improved by Nikoghosyan in terms of degree sequences: (3) if G is a 2-connected graph, then c ¸ minfn; d± +d±+1g; (4) every graph with d± + d±+1 ¸ n is hamiltonian. In this paper we present the dominating cycle versions of these theorems: (i) if G is a 2-connected graph, then either c ¸ d± + d¾2 or c ¸ p ¡ 1 (that is G has a dominating cycle); (ii) every 2-connected graph with d± + d±+1 ¸ p ¡ 1 has a dominating cycle. The results are sharp.
; Пусть G является n вершинным графом с минимальной степенью ± и степенной последовательностью ± = d1 < d2 < < dn. Длина длиннейшего цикла обозначается через с, а длина длиннейшей цепи (число её вершин) - через p. В 1952 году Дирак доказал: (1) если G является 2-связным графом, то с > min{ n, 2di}; (2) если граф удовлетворяет условию di > n, то он является гамильтоновым. Недавно эти результаты были улучшены в терминах степенных последовательностей: (3) если G является 2-связным графом, то с > min{ n , d± + d±+1}; (4) если граф удовлетворяет условию d± + d±+1 > n, то он является гамильтоновым (Zh.G. Nikoghosyan, Degree Sequences and Long Cycles in Graphs, ArXiv:1711.04134). В настоящей работе представляются версии теорем (3) и (4) для доминантных циклов. Полученные результаты неулучшаемы.

Mathematical Problems of Computer Science

49

click here to follow the link

zhora@ipia.sci.am

Institute for Informatics and Automation Problems of NAS RA

2018

ASCI