Article ID Journal Published Year Pages File Type
4603784 Linear Algebra and its Applications 2007 8 Pages PDF
Abstract

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 und ihren Vergleich mit dem Naphtalin, Ann. Chem. 454 (1927) 121–324].

Related Topics
Physical Sciences and Engineering Mathematics Algebra and Number Theory