Fibonacci dimension of the resonance graphs of catacondensed benzenoid graphs

Abstract

The Fibonacci dimension ▫$\text{fdim}(G)$▫ of a graph ▫$G$▫ was introduced [in S. Cabello, D. Eppstein, S. Klavžar, The Fibonacci dimension of a graph Electron. J. Combin., 18 (2011) P 55, 23 pp] as the smallest integer ▫$d$▫ such that ▫$G$▫ admits an isometric embedding into ▫$\Gamma_d$▫, the ▫$d$▫-dimensional Fibonacci cube. The Fibonacci dimension of the resonance graphs of catacondensed benzenoid systems is studied. This study is inspired by the fact, that the Fibonacci cubes are precisely the resonance graphs of a subclass of the catacondensed benzenoid systems. Our results show that the Fibonacci dimension of the resonance graph of a catacondensed benzenoid system ▫$G$▫ depends on the inner dual of ▫$G$▫. Moreover, we show that computing the Fibonacci dimension can be done in linear time for a graph of this class.

Keywords

Fibonaccijeva dimenzija;benzenoidni sistemi;resonančni grafi;algoritem;Fibonacci dimension;benzenoid systems;resonance graphs;algorithm;

Data

Language:	English
Year of publishing:	2013
Typology:	1.01 - Original Scientific Article
Organization:	UM FNM - Faculty of Natural Sciences and Mathematics
UDC:	519.17
COBISS:	19832840
ISSN:	0166-218X
Views:	327
Downloads:	23
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
URN:	URN:SI:UM:
Type (COBISS):	Not categorized
Pages:	str. 2158-2168
Volume:	Vol. 161
Issue:	issue 13-14
Chronology:	2013
ID:	1477047