Cycles through prescribed vertices with large degree sum
type: Item
instance of: scholarly article
title: Cycles through prescribed vertices with large degree sum
zbMATH Open document ID: 0838.05071
DOI: 10.1016/0012-365X(94)00036-I
author: Katsuhiro Ota
published in: Discrete Mathematics
publication date: 1996-05-30T00:00:00Z
review text: Let \(G\) be a graph with vertex set \(V\) and let \(S\) be a set of vertices in \(G\). For vertices \(u\) and \(v\) of \(G\) define \(\kappa(u, v; G)\) to be the maximum number of disjoint paths from \(u\) to \(v\) in \(G\) and let \(\kappa(S; G)= \min\{\kappa(u, v; G)\mid u, v\in S\) and \(u\neq v\}\). Suppose \(S\) satisfies \(\kappa(S; G)\geq k\geq 2\). Denote by \(\sigma_{k+ 1}(S; G)\) the smallest degree sum of \(k+ 1\) independent vertices in \(S\). The author produces sharp lower bounds for \(\sigma_{k+ 1}(S; G)\) in terms of \(|V|\), \(k\) and the independence number of the induced subgraph \(G[S]\) to ensure that \(G\) has a cycle containing all vertices of \(S\). In particular, if \(G\) is \(k\)-connected, he gives bounds on \(\sigma_{k+ 1}(V; G)\) which guarantee that there is a Hamiltonian cycle.
reviewed by: Norman F. Quimpo
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C45
zbMATH DE Number: 810265
zbMATH Keywords: paths
zbMATH Keywords: bounds
zbMATH Keywords: independence number
zbMATH Keywords: cycle
zbMATH Keywords: Hamiltonian cycle
MaRDI profile type: Publication
cites work: Long cycles in graphs with large degree sums
cites work: Q5722820
cites work: Note on Hamilton Circuits
cites work: 2‐neighborhoods and hamiltonian conditions
full work available at URL: 0012-365x(94)00036-i
OpenAlex ID: W2151291961
description: scientific article; zbMATH DE number 810265