Glasnik Matematicki, Vol. 43, No.2 (2008), 243-252.

THE ANTI-KEKULÉ NUMBER OF THE INFINITE TRIANGULAR, RECTANGULAR AND HEXAGONAL GRIDS

Darko Veljan and Damir Vukičević

Department of Mathematics, University of Split, Nikole Tesle 12, HR-21000 Split, Croatia
e-mail: vukicevi@pmfst.hr

Abstract.   The anti-Kekulé number is the smallest number of edges that must be removed from a connected graph with a perfect matching so that the graph remains connected, but has no perfect matching. In this paper the values of the Anti-Kekulé numbers of the infinite triangular, rectangular and hexagonal grids are found, and they are, respectively, 9, 6 and 4.

2000 Mathematics Subject Classification.   05C90, 05C69.

Key words and phrases.   Perfect matching, grid, anti-Kekulé number.

DOI: 10.3336/gm.43.2.02

References:

1. B. Bollobás, Graph Theory. An introductory course, Graduate Texts in Mathematics 63, Springer-Verlag, New York-Berlin, 1979.
   MathSciNet

2. I. Gutman and O. E. Polansky, Mathematical Concepts in Organic Chemistry, Springer-Verlag, Berlin, 1986.
   MathSciNet

3. K. Kutnar, D. Marusic, J. Sedlar and D. Vukicevic, Anti-Kekulée number of leap-frog fullerenes, preprint.

4. L. Lovász and M. D. Plummer, Matching Theory, North-Holland Publishing Co., Amsterdam, 1986.
   MathSciNet

5. M. Randic, Aromaticity of Polycyclic Conjugated Hydrocarbons, Chem. Rev. 103 (2003), 3449-3606.
   CrossRef

6. R. Todescini and V. Consonni, Handbook of Molecular Descriptors, Wiley-VCH, Weinheim, 2000.

7. N. Trinajstic, Chemical Graph Theory, CRC Press, Boca Raton, 1992.
   MathSciNet

8. D. Veljan, Kombinatorna i diskretna matematika, Algoritam, Zagreb, 2001.

9. D. Vukicevic, Anti-Kekulé number of C60, preprint.

10. D. Vukicevic and N. Trinajstic, On the anti-forcing number of benzenoids, J. Math. Chem. 42 (2007), 575-583.
    MathSciNet     CrossRef

11. D. B. West, Introduction to Graph Theory, Prentice Hall, Inc., Upper Saddle River, NJ, 1996.
    MathSciNet