A new property of the Lovász number and duality relations between graph parameters

Publisher:
Elsevier
Publication Type:
Journal Article
Citation:
Discrete Applied Mathematics, 2017, 216 (3), pp. 489 - 501
Issue Date:
2017
Full metadata record
Files in This Item:
Filename Description Size
A new property of the Lovász number and duality relations.pdfPublished Version499.09 kB
Adobe PDF
© 2016 Elsevier B.V.We show that for any graph G, by considering "activation" through the strong product with another graph H, the relation α(G)≤θ(symbol)(G) between the independence number and the Lovász number of G can be made arbitrarily tight: Precisely, the inequality α(G(squared times)H)≤θ(symbol)(G(squared times)H)=θ(symbol)(G)θ(symbol)(H) becomes asymptotically an equality for a suitable sequence of ancillary graphs H.This motivates us to look for other products of graph parameters of G and H on the right hand side of the above relation. For instance, a result of Rosenfeld and Hales states that α(G(squared times)H)≤α*(G)α(H), with the fractional packing number α*(G), and for every G there exists H that makes the above an equality; conversely, for every graph H there is a G that attains equality.These findings constitute some sort of duality of graph parameters, mediated through the independence number, under which α and α* are dual to each other, and the Lovász number θ(symbol) is self-dual. We also show duality of Schrijver's and Szegedy's variants θ(symbol)- and θ(symbol)+ of the Lovász number, and explore analogous notions for the chromatic number under strong and disjunctive graph products.
Please use this identifier to cite or link to this item: