Object

Title: Degree Sequences and Dominating Cycles in2-Connected Graphs ; Степенные последовательности и доминантные циклыв 2-связных графах

Abstract:

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) для доминантных циклов. Полученные результаты неулучшаемы.

Publisher:

Mathematical Problems of Computer Science

Identifier:

oai:noad.sci.am:136016

ISSN:

0131-4645

Language:

English

Volume:

49

URL:

click here to follow the link

Additional Information:

zhora@ipia.sci.am

Affiliation:

Institute for Informatics and Automation Problems of NAS RA

Year:

2018

Indexing:

ASCI

Object collections:

Last modified:

May 3, 2021

In our library since:

Jul 29, 2020

Number of object content hits:

6

All available object's versions:

https://noad.sci.am/publication/149637

Show description in RDF format:

RDF

Show description in OAI-PMH format:

OAI-PMH

Objects

Similar

This page uses 'cookies'. More information