Independence number and \(k\)-trees of graphs
type: Item
instance of: scholarly article
title: Independence number and \(k\)-trees of graphs
zbMATH Open document ID: 1380.05155
author: Zheng Yan
published in: Graphs and Combinatorics
publication date: 2017-12-12T00:00:00Z
review text: Let \(G=(V,E)\) be a simple graph and let \(\alpha(G)\) and \(\kappa(G)\) denote the independence number and the connectivity of \(G\). For two vertices \(x\) and \(y\) of \(G\), the local connectivity \(\kappa_G(x,y)\) is defined to be the maximum number of internally disjoint paths connecting \(x\) and \(y\) and define \(\kappa_G(S):= \min\{\kappa_G(x,y): x,y\in S, x\neq y\}\), where \(S\) is a subset of \(V(G)\). The author in this paper has shown that if \(\alpha(G)\leq (k-1)\kappa_G(S)+1\), then \(G\) has a tree which contain \(S\) and its maximum degree is at most \(k\). Moreover this condition is sharp.
reviewed by: Saeid Alikhani
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 6817801
zbMATH Keywords: independence number
zbMATH Keywords: \(k\)-tree
MaRDI profile type: Publication
full work available at URL: s00373-017-1821-4
OpenAlex ID: W2626979389
cites work: A note on Hamiltonian circuits
cites work: A degree sum condition concerning the connectivity and the independence number of a graph
cites work: A \(k\)-tree containing specified vertices
cites work: Spanning trees with bounded degrees
cites work: Cycles in graphs with prescribed stability number and connectivity
DOI: 10.1007/S00373-017-1821-4
description: scientific article; zbMATH DE number 6817801