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...

Full description

Saved in:
Bibliographic Details
Published in:Linear algebra and its applications 2007-01, Vol.420 (2), p.441-448
Main Authors: Abeledo, Hernán, Atkinson, Gary W.
Format: Article
Language:English
Subjects:
Algebra
Clar number
Exact sciences and technology
Fries number
Linear and multilinear algebra, matrix theory
Mathematics
Plane bipartite graphs
Polyhedral combinatorics
Sciences and techniques of general use
Unimodular matrices
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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].
ISSN:0024-3795
1873-1856
DOI:10.1016/j.laa.2006.07.026