The Fibonacci dimension of a graph

MaRDI QIDQ540035zbMATH OpenFDO

Authors S. Cabello, Sandi Klavžar, David Eppstein

Publication date 1 June 2011

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/232532, http://www.emis.de/journals/EJC/Volume_18/Abstracts/v18i1p55.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Mathematics Subject Classification ID

Distance in graphs (05C12) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85)

Review text

Summary: The Fibonacci dimension fdim\((G)\) of a graph \(G\) is introduced as the smallest integer \(f\) such that \(G\) admits an isometric embedding into \(\Gamma_f\), the \(f\)-dimensional Fibonacci cube. We give bounds on the Fibonacci dimension of a graph in terms of the isometric and lattice dimension, provide a combinatorial characterization of the Fibonacci dimension using properties of an associated graph, and establish the Fibonacci dimension for certain families of graphs. From the algorithmic point of view, we prove that it is NP-complete to decide whether fdim\((G)\) equals the isometric dimension of \(G\), and show that no algorithm to approximate fdim\((G)\) has approximation ratio below 741/740, unless P=NP. We also give a (3/2)-approximation algorithm for fdim\((G)\) in the general case and a \((1 + \epsilon)\)-approximation algorithm for simplex graphs.

Recommendations

• Fibonacci dimension of the resonance graphs of catacondensed benzenoid graphs
• Linear recognition and embedding of Fibonacci cubes
• Generalized Fibonacci cubes
• Structure of Fibonacci cubes: a survey
• scientific article; zbMATH DE number 10827

Cited in

(9)

• The fiber dimension of a graph
• Structure of Fibonacci cubes: a survey
• The degree sequence of Fibonacci and Lucas cubes
• Linear recognition and embedding of Fibonacci cubes
• Fibonacci dimension of the resonance graphs of catacondensed benzenoid graphs
• Vertex and edge orbits of Fibonacci and Lucas cubes
• The Plancherel measure of the Young–Fibonacci graph
• Partial cubes and Fibonacci dimension: insights and perspectives
• A family of partial cubes with minimal Fibonacci dimension

This page was built for publication: The Fibonacci dimension of a graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q540035)