Undirected Graphs of Entanglement 3

Details Undirected Graphs of Entanglement 3 Undirected Graphs of Entanglement 3

2009-04-10

arxiv.org/abs/0904.1696v1

Computer Science

Computer Science and Game Theory

33 pages

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Undirected Graphs of Entanglement 3 does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Undirected Graphs of Entanglement 3, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Undirected Graphs of Entanglement 3 will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-674057