Unimodularity of the Clar number problem

We study the generalization to bipartite and 2-connected plane graphs of the Clar number, an optimization model proposed by Clar {[}E. Clar, The Aromatic Sextet, John Wiley & Sons, London, 1972] to compute indices of benzenoid hydrocarbons. Hansen and Zheng {[}P. Hansen, M. Zheng, The Clar number of a benzenoid hydrocarbon and linear programming, J. Math. Chem. 15 (1994) 93-107] formulated the Clar problem as an integer program and conjectured that solving the linear programming relaxation always yields integral solutions. We establish their conjecture by proving that the constraint matrix of the Clar integer program is always unimodular. Interestingly, in general these matrices are not totally unimodular. Similar results hold for the Fries number, an alternative index for benzenoids proposed earlier by Fries {[}K. Fries, Uber Byclische Verbindungen and ihren Vergleich mit dem Naphtalin, Ann. Chem. 454 (1927) 121-324]. (c) 2006 Elsevier Inc. All rights reserved.