Computing the clar number of nanotubes and other fullerenes

Document Type : Full Length Article

Authors

1 Mathematics, Sciences Universidad Nacional de Colombia Bogota

2 Mathematics, Sciences, Universidad Nacional de Colombia, Bogota, Colombia

Abstract

We exhibit a polynomial time algorithm that computes the Clar number of any nanotube. This algorithm can be easily extended to one that computes the Clar number of fullerene whose pentagon-clusters are all of even size.

It is known that computing the Clar number of planar graphs is NP-hard. It is not known if computing the Clar number of fullerenes is a tractable problem. We show that the latter problem can be suitably approximated in polynomial time, and we also discuss the existence of fpt-algorithms for this important problem of Cheminformatics.

Graphical Abstract

Computing the clar number of nanotubes and other fullerenes

Keywords

Main Subjects


[1] H. Abeledo, G. Atkinson, Unimodularity of the Clar Number Problem, Linear Algebra Appl. 420
(2007) 441-448.
[2] M. Ahmadi, E. Farhadi, V. Khorasani, On computing the Clar number of a fullerene using optimization techniques, MATCH Commun. Math. Comput. Chem. 75 (2016) 695-701.
[3] E. Berczi-Kovacs, A. Bernath, The complexity of the Clar number problem and an FPT algorithm,
TR-2016-20. Egervary Research Group, www.cs.elte.hu/egres, 2016.
[4] E. Clar, The Aromatic Sextet,Wiley, New York, 1972.
[5] C. Dekker, Carbon nanotubes as molecular quantum wires, Physics Today 52 (5) (1999) 22-28.
[6] L. Esperet, F. Kardoˇs, A. King, D. Kr´al, Daniel, S. Norine, Exponentially many perfect matchings
in cubic graphs, Adv. Math. 227(4) (2012) 1646-1664.
[7] J. Flum , M. Grohe, Parameterized Complexity Theory, Springer Verlag, Heidelberg, 2006.
[8] P. Fowler, D. Manolopoulos, An Atlas of Fullerenes, Dover, NewYork, 2007.
[9] M. Ghorbani, E. Naserpour, The Clar Number of Fullerene C24n and Carbon Nanocone CNC44[n], Iran. J. Math. Chem. 2(1) (2011) 53-59.
[10] M. Jalali-Rad, Which fullerenes are stable?, J. math. nonosci. 5 (2015) 23-29.
[11] F. Kardoˇs, D. Kral, J. Miskuf, J. Sereni, Fullerene graphs have exponentially many perfect matching, J. Math. Chem. 46(2) (2009) 443–447.
[12] F. Kardoˇs, A computer-assisted proof of Barnette-Goodey conjecture: Not only fullerene graphs are Hamiltonian, SIAM J. Discret. Math. 34(1) (2020) 62–100.
[13] P. Kasteleyn, The statistics of dimers on a lattice I: The number of dimer arrangements on a
quadratic lattice, Physica 27(12) (1961) 1209–1225.
[14] H. Kroto, J. Heath, S. O’Brien, R. Curl, R. Smalley, C60 Buckminsterfullerene, Nature 318 (6042)
(1985) 162-163.
[15] H. Zhang, D. Ye, Y. Liu, A combination of Clar number and Kekul ´e count as an indicator of relative stability of fullerene isomers of C60, J. Math. Chem. 48 (2010) 733–740.
[16] H. Zhang, D. Ye, An upper bound for the Clar number of fullerene graphs, J. Math. Chem. 41(2) (2007) 123-133.
Volume 7, Issue 4
December 2022
Pages 209-221
  • Receive Date: 23 October 2022
  • Revise Date: 10 November 2022
  • Accept Date: 22 November 2022
  • Publish Date: 01 December 2022