Partial Cubes and Fibonacci Dimension: Insights and Perspectives
Partial Cubes and Fibonacci Dimension: Insights and Perspectives
A partial cube is a graph.G that can be isometrically embedded into a hypercube.Q(k), with the minimum of such k called the isometric dimension,.idim(G), of.G. A Fibonacci cube Gamma(k) excludes strings containing 11 from the vertices. Any partial cube.G embeds into some Gamma(d), defining Fibonacci dimension,.fdim(G), as the minimum of such d.It holds.idim(G) <= fdim(G) <= 2 center dot idim(G) - 1. While.idim(G) is computable in polynomial time, check whether.idim(G) = fdim(G) is NP-complete. We survey the properties of partial cubes and Generalized Fibonacci Cubes and present a new family of graphs.G for which.idim(G) = fdim(G). We conclude with some open problems.
- Università degli studi di Salerno Italy
- University of Rome Tor Vergata Italy
- University of Catania Italy
- University of Palermo Italy
Fibonacci Cubes, Fibonacci Cubes; Isometric words; Partial Cubes, Partial Cubes, Isometric words
Fibonacci Cubes, Fibonacci Cubes; Isometric words; Partial Cubes, Partial Cubes, Isometric words
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).0 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!