New results on \(k\)-independence of graphs
type: Item
instance of: scholarly article
title: New results on \(k\)-independence of graphs
zbMATH Open document ID: 1361.05097
author: Shimon Kogan
published in: The Electronic Journal of Combinatorics
publication date: 2017-05-18T00:00:00Z
full work available at URL: v24i2p15
review text: Summary: Let \(G = (V, E)\) be a graph and \(k \geq 0\) an integer. A \(k\)-independent set~\(S \subseteq G\) is a set of vertices such that the maximum degree in the graph induced by \(S\) is at most \(k\). Denote by \(\alpha_{k}(G)\) the maximum cardinality of a \(k\)-independent set of \(G\). For a graph \(G\) on \(n\) vertices and average degree \(d\), Turán's theorem asserts that \(\alpha_{0}(G) \geq \frac{n}{d+1}\), where the equality holds if and only if \(G\) is a union of cliques of equal size. For general \(k\) we prove that \(\alpha_{k}(G) \geq \dfrac{(k+1)n}{d+k+1}\), improving on the previous best bound \(\alpha_{k}(G) \geq \dfrac{(k+1)n}{ \lceil d \rceil+k+1}\) of \textit{Y. Caro} and \textit{A. Hansberg} [Electron. J. Comb. 20, No. 1, Research Paper P33, 17 p. (2013; Zbl 1266.05110)]. For \(1\)-independence we prove that equality holds if and only if \(G\) is either an independent set or a union of almost-cliques of equal size (an almost-clique is a clique on an even number of vertices minus a \(1\)-factor). For \(2\)-independence, we prove that equality holds~if and only if \(G\) is an independent set. Furthermore when \(d>0\) is an integer divisible by 3 we prove that \(\alpha_2(G) \geq \dfrac{3n}{d+3} \left( 1 + \dfrac{12}{5d^2 + 25d + 18} \right)\).
Mathematics Subject Classification ID: 05C69
zbMATH DE Number: 6719985
zbMATH Keywords: \(k\)-independent set
MaRDI profile type: Publication
cites work: Q3503433
cites work: Partitions of graphs into small and large sets
cites work: On a division property of consecutive integers
cites work: New approach to the \(k\)-independence number of a graph
cites work: Improved lower bounds on k‐independence
cites work: Low-degree Graph Partitioning via Local Search with Applications to Constraint Satisfaction, Max Cut, and Coloring
cites work: On \(k\)-domination and \(j\)-independence in graphs
cites work: Q4726281
cites work: Q3141900
cites work: Q5530470
cites work: Paths, Stars and the Number Three
cites work: Domination number in graphs with minimum degree two
cites work: Q5781249
Recommended article: New results on \(k\)-independence of hypergraphs
Recommended article: New approach to the \(k\)-independence number of a graph
Recommended article: New bounds on the independence number of connected graphs
Recommended article: On the \(k\)-independence number of graphs
Recommended article: On the \(k\)-independence number in graphs
Recommended article: A new lower bound on the independence number of graphs
Recommended article: New results on independent sets in extensions of \(2K_2\)-free graphs
Recommended article: Q4374002
Recommended article: Independence andk-domination in graphs
Recommended article: A new lower bound on the independence number of a graph and applications
description: scientific article; zbMATH DE number 6719985