Long cycles in 1-tough graphs with large degree sums
type: Item
instance of: scholarly article
title: Long cycles in 1-tough graphs with large degree sums
zbMATH Open document ID: 0785.05064
author: Jianping Li
author: Feng Tian
author: Lianzhu Zhang
published in: Chinese Science Bulletin
publication date: 1994-04-13T00:00:00Z
review text: Let \(c(G)\) denote the circumference of a graph \(G\). The following notations are used in the statements of results that are announced in this letter: \(\sigma_ 3(G)=\min\{\sum^ 3_{i=1} d(v_ i): \{v_ 1,v_ 2,v_ 3\}\) is an independent set in \(G\}\), \(\overline\sigma_ 3(G)=\min\{\sum^ 3_{i=1} d(v_ i)- |\bigcap^ 3_{i=1} N(v_ i)|: \{v_ 1,v_ 2,v_ 3\}\) is an independent set in \(G\}\), \(\rho_ 3(G)=\min\{|\bigcup^ 3_{i=1} N(v_ i)|: \{v_ 1,v_ 2,v_ 3\}\) is an independent set in \(G\}\), and \(\rho^*_ 3(G)=\min\{|\bigcup^ 3_{i=1} N(v_ i)|: \{v_ 1,v_ 2,v_ 3\}\) is an independent set in \(G\) with \(\bigcap^ 3_{i=1} N(v_ i)\neq\varnothing\}\). Results: Let \(G\) be a 1-tough graph of order \(n\). (a) If \(\sigma_ 3(G)\geq n\geq 3\), then \(c(G)\geq\min\{n,2\rho^*_ 3(G)+ 4\}\); consequently, \(c(G)\geq \min\{n,2\rho_ 3(G)+ 4\}\). (b) If \(\sigma_ 3(G)\geq (3n-13)/2\) for \(n\geq 15\) and odd, or \(\sigma_ 3(G)\geq (3n-16)/2\) for \(n\geq 16\) and even, or \(\sigma_ 3(G)\geq n\) where \(n\leq 14\), then \(G\) is Hamiltonian. (c) If \(\sigma_ 3(G)\geq n\geq 3\) and \(\rho^*_ 3(G)\geq (n-4)/2\), then \(G\) is Hamiltonian.
Mathematics Subject Classification ID: 05C45
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 436768
zbMATH Keywords: long cycles
zbMATH Keywords: 1-tough graphs
zbMATH Keywords: Hamiltonian graphs
zbMATH Keywords: circumference
zbMATH Keywords: independent set
reviewed by: S. F. Kapoor
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 436768