Independence number and \(k\)-trees of graphs (Q1684925)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Independence number and \(k\)-trees of graphs |
scientific article |
Statements
Independence number and \(k\)-trees of graphs (English)
0 references
12 December 2017
0 references
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.
0 references
independence number
0 references
\(k\)-tree
0 references
0 references