On the interrelation between synchronized and non-synchronized behaviour of Petri Nets

DOI10.25596/JALC-2019-003zbMATH Open1422.05072arXiv1808.01800OpenAlexW1880338612MaRDI QIDQ5235980

Bas Broere, Hans Zantema

Publication date: 14 October 2019

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$-cube is $k$-representable for every $kgeq1$. Our main technique consists of exploring occurrence based functions that replace every $i$th 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.

Full work available at URL: https://arxiv.org/abs/1808.01800

zbMATH Keywords

Cartesian product graphword representation\(k\)-dimensional cube

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Graph operations (line graphs, products, etc.) (05C76)

Related Items (2)

Minimum length word-representants of graph products ⋮ Word-representable graphs: orientations, posets, and bounds

This page was built for publication: On the interrelation between synchronized and non-synchronized behaviour of Petri Nets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5235980)