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 language | English |
|---|---|
| Pages (from-to) | 3-12 |
| Number of pages | 10 |
| Journal | Journal of Automata, Languages and Combinatorics |
| Volume | 24 |
| Issue number | 1 |
| DOIs | |
| Publication status | Published - 2019 |
Fingerprint
Keywords
- Cartesian product graph
- K-dimensional cube
- Word representation
Cite this
}
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 journal › Article › Academic › peer-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 -