Undirected Graphs of Entanglement 3
| dc.creator | Belkhir, Walid | |
| dc.date | 2009-04-10 | |
| dc.date.accessioned | 2026-07-07T13:02:27Z | |
| dc.date.available | 2026-07-07T13:02:27Z | |
| dc.description | Entanglement is a complexity measure of digraphs that origins in fixed-point logics. Its combinatorial purpose is to measure the nested depth of cycles in digraphs. We address the problem of characterizing the structure of graphs of entanglement at most $k$. Only partial results are known so far: digraphs for $k=1$, and undirected graphs for $k=2$. In this paper we investigate the structure of undirected graphs for $k=3$. Our main tool is the so-called \emph{Tutte's decomposition} of 2-connected graphs into cycles and 3-connected components into a tree-like fashion. We shall give necessary conditions on Tutte's tree to be a tree decomposition of a 2-connected graph of entanglement 3. | |
| dc.description | 33 pages | |
| dc.identifier | https://arxiv.org/abs/0904.1696 | |
| dc.identifier | http://arxiv.org/abs/0904.1696 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/226452 | |
| dc.subject | Computer Science and Game Theory | |
| dc.subject | Discrete Mathematics | |
| dc.title | Undirected Graphs of Entanglement 3 | |
| dc.type | text |