Институт Золотого Сечения - Математика Гармонии

Haruo Hosoya
Sequences of Polyomino and Polyhex Graphs
whose Perfect Matching Numbers
are Fibonacci or Lucas Numbers:
The Golden Family Graphs of a New Category
Abstract. Several sequences of graphs are introduced whose perfect matching numbers, or Kekule numbers, K{G), are either Fibonacci or Lucas numbers, or their multiples. Since the ratio of the AT(G)s of consecutive members converges to the golden ratio, these sequences of graphs belong to another class of golden family graphs.

1. Introduction

A graph, G, is a mathematical object composed of vertices, j V}, and edges {E}, where an edge spans a pair of vertices (Harary, 1969). A matching of a graph is a set of edges of G such that no two of them share a vertex in common. If a graph with even n = |V| has a matching with л/2 edges it is called a perfect matching graph. The number of possible perfect matchings of G is the perfect matching number, or Kekule number, K(G). Although a tree graph has at most one Kekule structure, a number of interesting features have been found for the K{G) numbers of polycyclic graphs (HOSOYA, 1986). In chemistry the K(G) of a polyhex graph, or hexagonal animal, reflects the stability of the parent polycyclic aromatic hydrocarbon molecule, such as, naphthalene orbenzopyrene (Cyvin and Gutman, 1988; Trinajstic, 1992). On the other hand, in solid state physics K(G) enumeration for giant polyominoes, or tetragonal animals, is an important subject for discussing the magnetic properties of metals and antiferromagnetic substances (Kasteleyn, 1967: Temperley, 1981). A variety of useful and interesting methods for enumerating K(G) of polyhex and polyomino graphs are proposed and discussed.

The present author has accumulated data of the K(G) numbers of both polyhexes (Yamaguchi et al., 1975; Hosoya et al., 1986) and polyominoes (Motoyama and Hosoya, 1976), and he also has proposed several mathematical techniques (Hosoya and Yamaguchi, 1976; Motoyama and Hosoya, 1977; Hosoya and Ohkami, 1983) useful for the study of these problems. Recently the concept of golden family graphs (Hosoya, 2005) for various sequences of graphs was proposed. Several new sequences of graphs were found whose topological indices (HOSOYA, 1971, 1973), Z, are equal to either Fibonacci or Lucas numbers, or their multiples. They are called golden family graphs, since the ratio Z-values of their consecutive members converges to the golden mean, τ.

The topological index Z is a characteristic quantity obtained by summing the non-adjacent numbers, p(G, k)s, or k-matching numbers, and K(G) is closely related to Z (HOSOYA, 1971, 1973). In this paper it will be shown that the K(G) numbers for several sequences of polyhex and polyomino graphs are Fibonacci or Lucas numbers, or their multiples, and the ratio of K(G)s of their consecutive terms converges to τ.

Full text see in PDF format (1.7Mb)

Haruo Hosoya, Sequences of Polyomino and Polyhex Graphs whose Perfect Matching Numbers are Fibonacci or Lucas Numbers: The Golden Family Graphs of a New Category // «Академия Тринитаризма», М., Эл № 77-6567, публ.13126, 22.03.2006

[Обсуждение на форуме «Наука»]