A degree sum condition concerning the connectivity and the independence number of a graph
type: Item
instance of: scholarly article
title: A degree sum condition concerning the connectivity and the independence number of a graph
zbMATH Open document ID: 1176.05044
author: Kenta Ozeki
author: Tomoki Yamashita
published in: Graphs and Combinatorics
publication date: 2009-04-29T00:00:00Z
review text: Let \(G\) be a graph \(S\subset V(G)\). We denote by \(\alpha(G)\) the maximum number of pairwise nonadjacent vertices in \(S\). For \(x,y\in V(G)\), the local connectivity \(k(x,y)\) is defined to be the maximum number of internally-disjoint path connecting \(x\) and \(y\) in \(G\). The authors define \(k(S)=\min\{k(x,y): x,y\in S, x\neq y\}\). If \(\alpha(S)\geq k\), let \(\sigma_k(S)= \min\{d_G(x)\) \(X\) is an independent set of \(S\) with \(|X|= k\}\); otherwise \(\sigma_k(S)= +\infty\), respectively. The authors proved the following theorem and showed that it is the best possible. Let \(G\) be a graph on \(n\) vertices, and \(S\subset V(G)\) with \(k(S)\geq 3\). If \(\sigma_4(S)\geq n+ k(S)+ \alpha(S)-1\), then \(S\) is cyclable in \(G\). The authors compare this result with previous ones and show that this degree condition is sharp and this gives a new degree sum condition for a three-connected graph to be Hamiltonian.
reviewed by: Ferdinand Gliviak
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 05C69
zbMATH DE Number: 5549542
zbMATH Keywords: connectivity
zbMATH Keywords: independence number of a graph
MaRDI profile type: Publication
full work available at URL: s00373-008-0802-z
OpenAlex ID: W2029635940
cites work: A generalization of a result of Häggkvist and Nicoghossian
cites work: A remark on two sufficient conditions for Hamilton cycles
cites work: Q4871748
cites work: Cycles through subsets with large degree sums
cites work: Cyclability of 3-connected graphs
cites work: Two sufficient conditions for dominating cycles
cites work: Note on Hamilton Circuits
cites work: Cycles through prescribed vertices with large degree sum
cites work: 2‐neighborhoods and hamiltonian conditions
DOI: 10.1007/S00373-008-0802-Z
Recommended article: A degree sum condition on the order, the connectivity and the independence number for Hamiltonicity
Recommended article: Degree sum and connectivity conditions for dominating cycles
Recommended article: The independence number of graphs in terms of degrees
Recommended article: A degree sum condition with connectivity for relative length of longest paths and cycles
Recommended article: Degree sum of a pair of independent edges and \(Z_{3}\)-connectivity
Recommended article: Generalized degree conditions for graphs with bounded independence number
Recommended article: Degree sums and proper connection number of graphs
Recommended article: Q5480718
Recommended article: Independence number of hypergraphs under degree conditions
Recommended article: A lower bound on the independence number of a graph in terms of degrees
description: scientific article; zbMATH DE number 5549542