A new lower bound on the independence number of a graph and applications

MaRDI QIDQ405126zbMATH OpenFDO

Authors Michael A. Henning, Christian Löwenstein, Justin Southey, A. Yeo

Publication date 4 September 2014

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

Full work available at URL http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i1p38

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

maximum clique size

Mathematics Subject Classification ID

Vertex degrees (05C07) Extremal problems in graph theory (05C35) Hypergraphs (05C65) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• On vertex independence number of uniform hypergraphs
• New results on \(k\)-independence of hypergraphs
• Independence in uniform linear triangle-free hypergraphs
• Bounds on the independence number of a graph in terms of order, size and maximum degree
• A note on the caro-tuza bound on the independence number of uniform hypergraphs

Cites work

• An upper bound for the transversal numbers of 4-uniform hypergraphs
• Domination in partitioned graphs
• scientific article; zbMATH DE number 3675940 (Why is no real title available?)
• Hypergraphs with large transversal number and with edge sizes at least 3
• Independence, clique size and maximum degree
• Matchings and transversals in hypergraphs, domination and independence in trees
• Small transversals in hypergraphs
• Total domination of graphs and small transversals of hypergraphs

Cited in

(25)

• A lower bound on the independence number of a graph
• A new upper bound on the total domination number in graphs with minimum degree six
• Zero forcing in claw-free cubic graphs
• Transversals and independence in linear hypergraphs with maximum degree two
• Lower bounds for the independence and \(k\)-independence number of graphs using the concept of degenerate degrees
• A lower bound on the independence number of a graph in terms of degrees and local clique sizes
• New Bounds of Induced Acyclic Graphoidal Decomposition Number of a Graph
• scientific article; zbMATH DE number 3989382 (Why is no real title available?)
• Improved lower bounds on k‐independence
• On vertex independence number of uniform hypergraphs
• New lower bounds on independence number in triangle-free graphs in terms of order, maximum degree and girth
• New bounds on the independence number of connected graphs
• An improved lower bound on the independence number of a graph
• Perfect Roman domination in regular graphs
• Bounds on the independence number of a graph in terms of order, size and maximum degree
• A new notion of vertex independence and rank for finite graphs
• New results on \(k\)-independence of graphs
• Packing in regular graphs
• Conjectures of TxGraffiti: independence, domination, and matchings
• A note on Reed's conjecture for triangle-free graphs
• The Tuza–Vestergaard Theorem
• Some bounds on the size of maximum G-free sets in graphs
• Lower bounds on the independence number of certain graphs of odd girth at least seven
• The packing number of cubic graphs
• On independent domination and packing numbers of subcubic graphs

This page was built for publication: A new lower bound on the independence number of a graph and applications

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