Return to Answer

This is quite relevant to my article Local Loop Lemma. I didn't know it is called De Bruijn graph back then, and I needed a slight modification for the paper but I essentially show that any digraph which is strongly connected and has directed walks of all lengths is a homomorphic image of a De Bruijn graph without loops -- see sections 3.1, 3.2 in the article.

To comment how the construction in the article differs from your question:

1. I only needed a homomorphism to exist (with certain properties), not necessarily it to be surjective. On the other hand, the construction in the paper had enough of freedom to be able to be modified to a surjective one.
2. The paper works with De Bruijn graph without loops. When loops are included, the condition simplifies even more: G is an image of a De Bruijn graph if and only if it is strongly connected, and contains a loop.

Whether a graph is strongly connected and has a loop is decidable in linear time. :-)

This is quite relevant to my article Local Loop Lemma. I didn't know it is called De Bruijn graph back then, and I needed a slight modification for the paper but I essentially show that any digraph which is strongly connected and has directed walks of all lengths is a homomorphic image of a De Bruijn graph without loops -- see sections 3.1, 3.2 in the article.

To comment how the construction in the article differs from your question:

1. I only needed a homomorphism to exist (with certain properties), not necessarily it to be surjective. On the other hand, the construction in the paper had enough of freedom to be able to be modified to a surjective one.
2. The paper works with De Bruijn graph without loops. When loops are included, the condition simplifies even more: G is an image of a De Bruijn graph if and only if it is strongly connected, and contains a loop.

Whether a graph is strongly connected and has a loop is decidable in linear time. :-)

Edit: Just later, I have noticed that the question is about graphs that have 2-colored edges, which was not the case in Local Loop Lemma. Then I am actually not sure if there is a simple characterization of images of De Bruijn graphs... (I can think about it)

This is quite relevant to my article Local Loop Lemma. I didn't know it is called De Bruijn graph back then, and I needed a slight modification for the paper but I essentially show that any digraph which is strongly connected and has directed walks of all lengths is a homomorphic image of a De Bruijn graph without loops -- see sections 3.1, 3.2 in the article.

To comment how the construction in the article differs from your question:

1. I only needed a homomorphism to exist (with certain properties), not necessarily it to be surjective. On the other hand, the construction in the paper had enough of freedom to be able to be modified to a surjective one.
2. The paper works with De Bruijn graph without loops. When loops are included, the condition simplifies even more: G is an image of a De Bruijn graph if and only if it is strongly connected, and contains a loop.

This is quite relevant to my article Local Loop Lemma. I didn't know it is called De Bruijn graph back then, and I needed a slight modification for the paper but I essentially show that any digraph which is strongly connected and has directed walks of all lengths is a homomorphic image of a De Bruijn graph without loops -- see sections 3.1, 3.2 in the article.

To comment how the construction in the article differs from your question:

1. I only needed a homomorphism to exist (with certain properties), not necessarily it to be surjective. On the other hand, the construction in the paper had enough of freedom to be able to be modified to a surjective one.
2. The paper works with De Bruijn graph without loops. When loops are included, the condition simplifies even more: G is an image of a De Bruijn graph if and only if it is strongly connected, and contains a loop.

Whether a graph is strongly connected and has a loop is decidable in linear time. :-)

This is quite relevant to my article Local Loop Lemma. I didn't know it is called De Bruijn graph back then, and I needed a slight modification for the paper but I essentially show that any digraph which is strongly connected and has directed walks of all lengths is a homomorphic image of a De Bruijn graph -- see sections 3.1, 3.2 in the article.

Checking such conditions is clearly decidable in polynomial time, maybe even linear time (there I am not sure).

This is quite relevant to my article Local Loop Lemma. I didn't know it is called De Bruijn graph back then, and I needed a slight modification for the paper but I essentially show that any digraph which is strongly connected and has directed walks of all lengths is a homomorphic image of a De Bruijn graph without loops -- see sections 3.1, 3.2 in the article.

To comment how the construction in the article differs from your question:

1. I only needed a homomorphism to exist (with certain properties), not necessarily it to be surjective. On the other hand, the construction in the paper had enough of freedom to be able to be modified to a surjective one.
2. The paper works with De Bruijn graph without loops. When loops are included, the condition simplifies even more: G is an image of a De Bruijn graph if and only if it is strongly connected, and contains a loop.