| Title: | On the Fibonacci dimension of partial cubes |
|---|
| Authors: | ID Vesel, Aleksander (Author) |
|---|
| Files: |  http://www.imfm.si/preprinti/PDF/01104.pdf
|
|---|
| Language: | English |
|---|
| Work type: | Not categorized |
|---|
| Organization: | FNM - Faculty of Natural Sciences and Mathematics
|
|---|
| Abstract: | The Fibonacci dimension fdim▫$(G)$▫ of a graph ▫$G$▫ was introduced in [S. Cabello, D. Eppstein and S. Klavžar, The Fibonacci dimension of a graph, submitted] as the smallest integer ▫$d$▫ such that $G$ admits an isometric embedding into ▫$Q_d$▫, the ▫$d$▫-dimensional Fibonacci cube. A somewhat new combinatorial characterization of the Fibonacci dimension is given, which enables more comfortable proofs of some previously known results. In the second part of the paper 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. The main result shows 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: | matematika, teorija grafov, Fibonaccijeva dimenzija, delne kocke, resonančni grafi, benzenoidni sistemi, mathematics, graph theory, Fibonacci dimension, partial cubes, resonance graphs, benzenoid systems |
|---|
| Year of publishing: | 2009 |
|---|
| Number of pages: | str. 1-9 |
|---|
| Numbering: | Vol. 47, št. 1104 |
|---|
| PID: | 20.500.12556/DKUM-51805  |
|---|
| ISSN: | 1318-4865 |
|---|
| UDC: | 519.17 |
|---|
| COBISS.SI-ID: | 15310681 |
|---|
| NUK URN: | URN:SI:UM:DK:M276KAJO |
|---|
| Publication date in DKUM: | 10.07.2015 |
|---|
| Views: | 1408 |
|---|
| Downloads: | 53 |
|---|
| Metadata: |    |
|---|
| Categories: | Misc.
|
|---|
|
:
|
Copy citation |
|---|
| | | | Average score: | (0 votes) |
|---|
| Your score: | Voting is allowed only for logged in users. |
|---|
| Share: |  |
|---|
Hover the mouse pointer over a document title to show the abstract or click
on the title to get all document metadata. |
