Regular independent sets

DOI10.1016/J.DAM.2015.09.020MaRDI QIDQ260019zbMATH OpenOpenAlexFDO

Authors Yair Caro, Adriana Hansberg, Ryan Pepper

Publication date 18 March 2016

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1306.5026

zbMATH Keywords

independence\(k\)-degenerate graphs\(k\)-independence\(k\)-treesplanar graphsregular independence

Mathematics Subject Classification ID

Trees (05C05) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Planar graphs; geometric and topological aspects of graph theory (05C10) Vertex degrees (05C07)

Abstract: The regular independence number, introduced by Albertson and Boutin in 1990, is the size of a largest set of independent vertices with the same degree. Lower bounds were proven for this invariant, in terms of the order, for trees and planar graphs. In this article, we generalize and extend these results to find lower bounds for the regular $k$-independence number for trees, forests, planar graphs, $k$-trees and $k$-degenerate graphs.

Recommendations

• Lower bounds for constant degree independent sets
• The independence number of graphs with large odd girth
• The number of independent sets in a regular graph
• Independent domination in regular graphs
• scientific article; zbMATH DE number 4049676

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3043302 (Why is no real title available?)
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• Bounded-degree independent sets in planar graphs
• Deciding Clique-Width for Graphs of Bounded Tree-Width
• Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency
• Every planar map is four colorable. I: Discharging
• Every planar map is four colorable. II: Reducibility
• Face covers and the genus problem for apex graphs
• Fair domination in graphs
• Geometric algorithms and combinatorial optimization
• Graph-Theoretic Concepts in Computer Science
• Large induced forests in sparse graphs
• Linear time solvable optimization problems on graphs of bounded clique-width
• Lower bounds for constant degree independent sets
• New approach to the \(k\)-independence number of a graph
• On \(k\)-domination and \(j\)-independence in graphs
• On the Relationship Between Clique-Width and Treewidth
• Repetition number of graphs

Cited in

(5)

• A bound on the values of independence polynomials at -1/k for k-degenerate graphs
• Equating two maximum degrees
• Irregular independence and irregular domination
• Upper bounds on the \(k\)-forcing number of a graph
• Large induced subgraphs with three repeated degrees

This page was built for publication: Regular independent sets

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