Independence and the Havel-Hakimi residue

DOI10.1016/0012-365X(92)00479-BzbMath0805.05082OpenAlexW2089356095MaRDI QIDQ1322229

Daniel J. Kleitman, Jerrold R. Griggs

Publication date: 9 June 1994

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

Full work available at URL: https://doi.org/10.1016/0012-365x(92)00479-b

zbMATH Keywords

greedy algorithmindependence numberindependent setsHavel-Hakimi theoremresiduedegree sequences

Mathematics Subject Classification ID

Special sequences and polynomials (11B83) Graph theory (05C99)

Related Items (13)

Bounding the locating-total domination number of a tree in terms of its annihilation number ⋮ Graphs with the strong Havel-Hakimi property ⋮ The annihilation number does not bound the 2-domination number from the above ⋮ Relating the annihilation number and the 2-domination number of a tree ⋮ Automated conjecturing. III. Property-relations conjectures ⋮ Automated conjecturing. I: Fajtlowicz's Dalmatian heuristic revisited ⋮ Semi-regular graphs of minimum independence number ⋮ Relating the annihilation number and the 2-domination number of block graphs ⋮ Relating the total domination number and the annihilation number of cactus graphs and block graphs ⋮ MAX for \(k\)-independence in multigraphs ⋮ Havel-Hakimi residues of unigraphs ⋮ A lower bound on the independence number of a graph ⋮ New analytical lower bounds on the clique number of a graph

Uses Software

• GRAFFITI

Cites Work

• On conjectures of Graffiti
• Approximation algorithms for combinatorial problems
• Lower bounds on the independence number in terms of the degrees
• A remark on the existence of finite graphs
• On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I
• On the residue of a graph

This page was built for publication: Independence and the Havel-Hakimi residue