Group for Research in Decision Analysis


Numerical Bounds for the Perfect Matching Vector of a Polyhex


Consider a polyhex H which admits a perfect matching M. Harary, Klein and Zivkovic define the perfect matching vector of M as where nj is the number of hexagons of H containing exactly j edges of M (j=3,2,1,0). Sharp lower and upper bounds on and n0 for a given H and all M are obtained by mixed-integer programming. Computational experience with polyhexes having over one hundred hexagons is reported.

, 16 pages