a min–max theorem for plane bipartite graphs -凯发官网入口

discrete applied mathematics 158 (2010) 375–378contents lists available at sciencedirectdiscrete applied mathematicsjournal homepage: www.elsevier.com/locate/dama min–max theorem for plane bipartite graphshernán abeledo a, ∗ , gary w. atkinson ba department of engineering management and systems engineering, the george washington university, 1776 g street nw, washington, dc 20052, united statesb bell laboratories, alcatel-lucent, 600 mountain avenue, murray hill, nj, 07974-0636, united statesa r t i c l e i n f oarticle history:received 6 november 2007received in revised form 28 october 2009accepted 6 november 2009available online 9 december 2009keywords:plane bipartite graphsclar numbercombinatorial dualnetwork flowsa b s t r a c twe consider a partitioning problem, defined for bipartite and 2-connected plane graphs,whereeachnodeshouldbecoveredexactlyoncebyeitheranedgeorbyacyclesurroundinga face. the objective is to maximize the number of face boundaries in the partition. thisproblem arises in mathematical chemistry in the computation of the clar number ofhexagonal systems. in this paper we establish that a certain minimum weight coveringproblem of faces by cuts is a strong dual of the partitioning problem. our proof relieson network flow and linear programming duality arguments, and settles a conjectureformulatedbyhansenandzhenginthecontextofhexagonalsystems[p.hansen,m.zheng,upper bounds for the clar number of benzenoid hydrocarbons, journal of the chemicalsociety, faraday transactions 88 (1992) 1621–1625].© 2009 elsevier b.v. all rights reserved.1. introductionin this paper we study a node set partitioning problem defined on 2-connected plane bipartite graphs which have aperfect matching. in this optimization problem, edges or faces are used to cover the nodes and the objective is to maximizethe number of faces in the partition. this problem arises in chemical graph theory in the computation of the clar number ofa benzenoid system (or hexagonal system), which is a 2-connected subgraph of the hexagonal lattice that admits a perfectmatching.hansen and zheng [7] formulated the clar number as an integer programming problem and conjectured that their for-mulationhadtheintegralityproperty.abeledoandatkinson[1]settledthisconjecturebyprovingthattheconstraintmatrixof the clar integer program is unimodular. though this matrix may not be totally unimodular, in our case unimodularity issufficient to assure polyhedral integrality since all the linear constraints, with exception of the nonnegativity restrictions,are equations. thus, the clar number can be computed in polynomial time using linear programming methods.in another paper, hansen and zheng [8] considered a minimization problem for benzenoid systems that we call here theminimum weight cut cover problem. they showed that the optimal value of the cover problem is an upper bound for theclar number and conjectured that equality always holds. in this paper we use a network flow formulation of the cut coverproblem to prove their conjecture. as a consequence, the clar number and a minimum weight cut cover can be found inpolynomial time by solving a minimum cost network flow problem.the paper is organized as follows. in section 2 we provide essential definitions and present a linear programmingformulation for the clar problem. the cut cover problem is defined in section 3, where we also prove that it is a strong dualto the clar problem. the results in this paper appear in the extended abstracts [2,3] and are part of the doctoral dissertationby atkinson.∗corresponding author. tel.: 1 202 994 7521; fax: 1 202 994 0245.e-mail addresses: abeledo@gwu.edu (h. abeledo), atkinson@lucent-alcatel.com (g.w. atkinson).0166-218x/$ – see front matter © 2009 elsevier b.v. all rights reserved.doi:10.1016/j.dam.2009.11.004