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

Fingerprint

Regular hexahedron
Vertex of a graph
Concatenation
Cartesian product
Graph in graph theory
Complete Graph
Alternate
Strings
Distinct
Theorem

Keywords

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

Cite this

@article{95999604438f4cb29fd8e9f451acfbfb,
title = "The k-dimensional cube is k-representable",
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.",
keywords = "Cartesian product graph, K-dimensional cube, Word representation",
author = "Bas Broere and Hans Zantema",
year = "2019",
doi = "10.25596/jalc-2019-003",
language = "English",
volume = "24",
pages = "3--12",
journal = "Journal of Automata, Languages and Combinatorics",
issn = "1430-189X",
publisher = "Institut fur Informatik, Justus-Liebig-Universitat Giessen",
number = "1",

}

The k-dimensional cube is k-representable. / Broere, Bas; Zantema, Hans.

In: Journal of Automata, Languages and Combinatorics, Vol. 24, No. 1, 2019, p. 3-12.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - The k-dimensional cube is k-representable

AU - Broere, Bas

AU - Zantema, Hans

PY - 2019

Y1 - 2019

N2 - 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.

AB - 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.

KW - Cartesian product graph

KW - K-dimensional cube

KW - Word representation

UR - http://www.scopus.com/inward/record.url?scp=85070748180&partnerID=8YFLogxK

U2 - 10.25596/jalc-2019-003

DO - 10.25596/jalc-2019-003

M3 - Article

VL - 24

SP - 3

EP - 12

JO - Journal of Automata, Languages and Combinatorics

JF - Journal of Automata, Languages and Combinatorics

SN - 1430-189X

IS - 1

ER -