### Uittreksel

Taal | Engels |
---|---|

Pagina's | 3-12 |

Aantal pagina's | 10 |

Tijdschrift | Journal of Automata, Languages and Combinatorics |

Volume | 24 |

Nummer van het tijdschrift | 1 |

DOI's | |

Status | Gepubliceerd - 2019 |

### Vingerafdruk

### Citeer dit

*Journal of Automata, Languages and Combinatorics*,

*24*(1), 3-12. DOI: 10.25596/jalc-2019-003

}

*Journal of Automata, Languages and Combinatorics*, vol. 24, nr. 1, blz. 3-12. DOI: 10.25596/jalc-2019-003

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

Onderzoeksoutput: Bijdrage aan tijdschrift › Tijdschriftartikel › 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. Keywords: k-dimensional cube, word representation, cartesian product graph

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. Keywords: k-dimensional cube, word representation, cartesian product graph

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

T2 - Journal of Automata, Languages and Combinatorics

JF - Journal of Automata, Languages and Combinatorics

SN - 1430-189X

IS - 1

ER -