The k-dimensional cube is k-representable

Bas Broere, Hans Zantema

Research output: Contribution to journalArticleAcademicpeer-review

Abstract

A graph is called k-representable if there exists a word w over the nodes of the graph, each node occurring exactly k times, such that there is an edge between two nodes x, y if and only after removing all letters distinct from x, y, from w, a word remains in which x, y alternate. We prove that if G is k-representable for k > 1, then the Cartesian product of G and the complete graph on n nodes is (k + n − 1)-representable. As a direct consequence, the k-dimensional cube is k-representable for every k ≥ 1. Our main technique consists of exploring occurrence-based functions that replace every ith occurrence of a symbol x in a word w by a string h(x, i). The representing word we construct to achieve our main theorem is purely composed from concatenation and occurrence-based functions.

Original languageEnglish
Pages (from-to)3-12
Number of pages10
JournalJournal of Automata, Languages and Combinatorics
Volume24
Issue number1
DOIs
Publication statusPublished - 2019

Keywords

  • Cartesian product graph
  • K-dimensional cube
  • Word representation

Fingerprint Dive into the research topics of 'The k-dimensional cube is k-representable'. Together they form a unique fingerprint.

  • Cite this