کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
427273 | 686479 | 2012 | 5 صفحه PDF | دانلود رایگان |
The residue r(G)r(G) of a graph G is the number of zeros left after fully reducing the degree sequence of G via the Havel–Hakimi algorithm. The residue is one of the best known lower bounds on the independence number of a graph in terms of the degree sequence. Though this bound may be arbitrarily weak for graphs in general, we show that if G is the unique realization of its degree sequence, then the independence number of G is either r(G)r(G) or r(G)+1r(G)+1, and we characterize the unigraphs corresponding to each value.
► We compare Havel–Hakimi residues and independence numbers for unigraphs.
► We show how the residue behaves in relation to the canonical decomposition of a graph.
► The independence number of a unigraph is either equal to or 1 more than its residue.
Journal: Information Processing Letters - Volume 112, Issues 1–2, 15 January 2012, Pages 44–48