Top

Journal of Combinatorial Optimization

Published in:

21-09-2015

Code for polyomino and computer search of isospectral polyominoes

Authors: Xiaodong Liang, Rui Wang, Ji xiang Meng

Published in: Journal of Combinatorial Optimization | Issue 1/2017

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

A new code, binary 2-dimentional code (B2DC), is proposed for polyominoes. An algorithm based on the B2DC and the reverse search method are proposed for enumerating nonisomorphic planar simply connected polyominoes. An enumeration tree and a new father-son relationship are defined for enumerating polyominoes. Then we propose an algorithm to build adjacent matrices and laplacian matrices by B2DCs of polyominoes and search isospectral polyomino graphs by computing characteristic polynomials of those matrices.

previous article Neighbor product distinguishing total colorings

next article Total coloring of planar graphs without adjacent short cycles

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Avis D, Fukuda K (1996) Reverse search for enumeration. Discret Appl Math 65:21–46MathSciNetCrossRefMATH

Babić D, Gutman I (1992) On isospectral benzenoid graphs. J Math Chem 9:261–278CrossRef

Babić D (1993) Isospectral benzenoid graphs with an odd number of vertices. J Math Chem 12:137–146MathSciNetCrossRef

Caporossi G, Hansen P (1998) Enumeration of Polyhex Hydrocarbons to h=21. J Chem Inf Comput Sci 38:610–619CrossRef

Cioslowski J (1991) A conjecture on benzenoid graphs. J Math Chem 6:111–111CrossRef

Conway AR (1995) Enumerating 2D percolation series by the finite lattice method. J Phys A Math Gen 28:335–349CrossRefMATH

Conway AR, Guttmann AJ (1995) On two-dimensional percolation. J Phys A Math Gen 28:891–904CrossRefMATH

Golomb S (1994) Polyominoes: puzzles, patterns, problems and packings, Second edn. Princeton University Press, PrincetionMATH

Gutman I, Marković S, Grbović V (1991) The smallest pair of isospectral benzenoid systems. J Serb Chem Soc 56:553–554

Hansen P, Lebatteux C, Zheng M (1996) The boundary-edges code for polyhexes. Theochem J Mol Struct 363:237–247CrossRef

Harary F, Palmer E (1973) Graphical enumeration. Academic Press, New YorkMATH

Jensen I (2001) Enumerations of lattice animals and trees. J Stat Phys 102:865–881MathSciNetCrossRefMATH

Jensen I, Guttmann AJ (2000) Statistics of lattice animals (polyominoes) and polygons. J Phys A 33:L257–L263MathSciNetCrossRefMATH

Jensen I (2003) Counting polyominoes: a parallel implementation for cluster computing. LNCS 2659:203–212

Liang X, Meng J (2011) Computer search for isospectral benzenoid graphs. MATCH Commun Math Comput Chem 65:427–430MathSciNetMATH

Mertens S (1990) Lattice animals: A fast enumeration algorithm and new perimeter polynomials. J Stat Phys 58:1095–1108MathSciNetCrossRef

Oliveira e Silva T (2015) http://sweet.ua.pt/tos/animals/a44.html. Accessed 19 Dec 2014

Redelmeier DH (1981) Counting polyominoes: yet another attack. Discret Math 36:191–203MathSciNetCrossRefMATH

Zheng S, Wang Z, Zhang J, Xin X (1996) A result of searching for isospectral benzenoid graphs. J Xinjiang Univ (Nat Sci Ed) 13:21,28

Title: Code for polyomino and computer search of isospectral polyominoes
Authors: Xiaodong Liang
Rui Wang
Ji xiang Meng
Publication date: 21-09-2015
Publisher: Springer US
Published in: Journal of Combinatorial Optimization / Issue 1/2017
Print ISSN: 1382-6905
Electronic ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-015-9953-z

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 1/2017

On the kidney exchange problem: cardinality constrained cycle and chain problems on directed graphs: a survey of integer programming approaches

A solution to a conjecture on the generalized connectivity of graphs

Almost separable matrices

Maximal independent sets in a generalisation of caterpillar graph

On consecutive edge magic total labelings of connected bipartite graphs

Total weight choosability of Mycielski graphs

Premium Partner