New approach to the k-independence number of a graph

MaRDI QIDQ1953418zbMATH OpenFDO

Authors Yair Caro, Adriana Hansberg

Publication date 7 June 2013

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1208.4734, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i1p33

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

\(k\)-independenceaverage degree

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Abstract: Let $G=(V,E)$ be a graph and $kge0$ an integer. A $k$-independent set $SsubseteqV$ is a set of vertices such that the maximum degree in the graph induced by $S$ is at most $k$. With $alph{a}_k(G)$ we denote the maximum cardinality of a $k$-independent set of $G$. We prove that, for a graph $G$ on $n$ vertices and average degree $d$, $alph{a}_k(G)gefrack+1lceildceil+k+1n$, improving the hitherto best general lower bound due to Caro and Tuza [Improved lower bounds on k-independence, J. Graph Theory 15 (1991), 99-107].

Review text

Summary: Let \(G\) = (\(V,E\)) be a graph and \(k \geq 0\) an integer. A \(k\)-independent set \(S \subseteq V\) is a set of vertices such that the maximum degree in the graph induced by \(S\) is at most \(k\). With \(\alpha_k(G)\) we denote the maximum cardinality of a \(k\)-independent set of \(G\). We prove that, for a graph \(G\) on \(n\) vertices and average degree \(d, \alpha_k(G) \geq \frac{k+1}{\lceil d \rceil + k + 1} n\), improving the hitherto best general lower bound due to \textit{Y. Caro} and \textit{Z. Tuza} [J. Graph Theory 15, No. 1, 99--107 (1991; Zbl 0753.68079)].

Recommendations

• New results on \(k\)-independence of graphs
• New results on \(k\)-independence of hypergraphs
• Graphs with given k-independence number
• On the k-independence number in graphs
• Sharp upper bounds on the \(k\)-independence number in graphs with given minimum and maximum degree

Cited in

(30)

• The independence number of dense graphs with large odd girth
• Generalized transversals, generalized vertex covers and node-fault-tolerance in graphs
• Mixed domination and 2-independence in trees
• New results on independent sets in extensions of \(2K_2\)-free graphs
• MAX for \(k\)-independence in multigraphs
• On the \(k\)-independence number of graphs
• Transversals and independence in linear hypergraphs with maximum degree two
• On \(k\)-domination and \(j\)-independence in graphs
• Partitions of graphs into small and large sets
• Regular independent sets
• Lower bounds for the independence and \(k\)-independence number of graphs using the concept of degenerate degrees
• Sharp upper bounds on the \(k\)-independence number in graphs with given minimum and maximum degree
• New results on \(k\)-independence of hypergraphs
• Thresholds for the monochromatic clique transversal game
• A characterization of trees for a new lower bound on the k-independence number
• Degree sequence index strategy
• Isolation in graphs
• Multiple domination
• On the k-residue of disjoint unions of graphs with applications to k-independence
• On vertex independence number of uniform hypergraphs
• Graphs with given k-independence number
• Upper bounds on the \(k\)-forcing number of a graph
• Simultaneous domination in graphs
• Independent sets in graphs
• Partial domination -- the isolation number of a graph
• A new notion of vertex independence and rank for finite graphs
• New results on \(k\)-independence of graphs
• Conjectures of TxGraffiti: independence, domination, and matchings
• The k‐path vertex cover: General bounds and chordal graphs
• Complexity results on \(k\)-independence in some graph products

This page was built for publication: New approach to the \(k\)-independence number of a graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1953418)