  Among the classical models for interconnection networks are hypercubes and
Fibonacci cubes. Fibonacci cubes are induced subgraphs of hypercubes obtained
by restricting the vertex set to those binary strings which do not contain
consecutive 1s, counted by Fibonacci numbers. Another set of binary strings
which are counted by Fibonacci numbers are those with a restriction on the
runlengths. Induced subgraphs of the hypercube on the latter strings as
vertices define Fibonacci-run graphs. They have the same number of vertices as
Fibonacci cubes, but fewer edges and different connectivity properties.
  We obtain properties of Fibonacci-run graphs including the number of edges,
the analogue of the fundamental recursion, the average degree of a vertex,
Hamiltonicity, special degree sequences, and the number of hypercubes they
contain. A detailed study of the degree sequences of Fibonacci-run graphs is
interesting in its own right and is reported in a companion paper.
