4
$\begingroup$

Let $G$ be a digraph such that there is an unique directed walk of length $k$ between any two vertices. Equivalently, if $A$ is the adjacency matrix of $G$, then $A^k$ is the matrix with all entries $1$.

Then it is not too hard to show, using algebraic methods, that the number of vertices is $d^k$ for some integer $d$, that each vertex has indegree and outdegree $d$ and that $G$ has $d$ loops. Let's call such a digraph a $(d,k)$-nice digraph.

A simple example of a $(d,k)$-nice digraph is the de Bruijn graph for words of lenght $k$ over an alphabet of $d$ symbols. Note also that, if $G$ is a $(d,k)$-nice digraph, then the line digraph of $G$ is a $(d,k+1)$-nice digraph.

There are however, other examples than de Bruijn graphs. The following digraph, for example, is $(3,2)$-nice: http://graphonline.ru/en/?graph=iuDxicdebMgXCAFE. This example is, unfortunately, very asymmetric and doesn't seem to have a simple interpretation like de Bruijn graphs.

My questions are:

  • Does this class of digraphs have already been studied?
  • Is there a way to classify all $(d,k)$-nice graphs?
  • If there is no simple classification in the general case (which seems plausible given the irregular example I gave), can we hope to have a classification for specific values of $d$? In particular, can we find examples of $(2,k)$-nice digraphs that are not de Bruijn?
  • Are there any other interesting properties that we can prove that these digraphs have?
Improve this question
$\endgroup$
9
  • 2
    $\begingroup$ Exercise 5.74 in my book Enumerative Combinatorics, vol. 2, and Exercise 10.8 in my book Algebraic Combinatorics, second ed., are devoted to this topic. It's easy to compute the eigenvalues and number of Eulerian tours of $G$. My guess is that a classification is hopeless. The solution to Exercise 5.74 gives a method for constructing such graphs if multiple edges are allowed. $\endgroup$
    – Richard Stanley
    Commented Jul 18, 2020 at 0:11
  • $\begingroup$ Yes, I precisely found this problem while reading your book Algebraic Combinatorics! (very good book by the way) I found the problem very interesting and wanted investigate it more deeply, that's why I wanted to know if some research had already been done about it and if some form of classification was realistic. Also I don't see how we could allow multiple edges: doesn't a double edge necessarily create two paths of length k with the same start and end? $\endgroup$
    – Antoine Labelle
    Commented Jul 18, 2020 at 1:44
  • $\begingroup$ You are right, I was the considering the more general problem where there are $j$ paths of length $k$ between any two vertices, for fixed $j,k\geq 1$. $\endgroup$
    – Richard Stanley
    Commented Jul 18, 2020 at 3:12
  • $\begingroup$ I am a little confused about the terminology. For me, "path" is a certain sequence of vertices without repetition. But the power of the adjacency matrix counts all walk, that is, with repetition. Is your question about what I refer to as "walks"? $\endgroup$
    – M. Winter
    Commented Jul 19, 2020 at 10:34
  • $\begingroup$ Yes, I meant walk, we don't bother about repetition (I didn't knew that path was only for distinct vertices). I'll change this $\endgroup$
    – Antoine Labelle
    Commented Jul 19, 2020 at 16:10

1 Answer 1

Reset to default
2
$\begingroup$

Your irregular $(3,2)$-nice graph is almost a De Bruijn graph.

Label the vertices ($0$ to $8$) with $12,21,11,22,10,02,20,01,00.$ Then the deviations are that your edges $$1\rightarrow 6 \ \&\ 3\rightarrow 4 \mbox{ should be switched to edges } 1\rightarrow 4\ \& \ 3\rightarrow 6.$$ i.e. $$21\rightarrow 20\ \&\ 22\rightarrow 10 \mbox{ should be switched to }21\rightarrow 10\ \&\ 22\rightarrow 20. $$ You might think about similar switching. Given the $(d,k)$-nice De Bruijn Graph, consider all switches of $$p_1 \rightarrow q_1\ \& \ p_2 \rightarrow q_2 \mbox{ to } p_1 \rightarrow q_2\ \&\ p_2 \rightarrow q_1 $$which preserve $(d,k)$-niceness. Do the same for each of the resulting graphs. In the end you might have a digraph with nodes labelled by (some) $(d,k)$ nice graphs, maybe all. This might allow the generation of these graphs.

Is it the case that the $d$ loops must stay fixed? What about the $\binom{d}{2}$ digons like $ ab \leftrightarrow ba$ for $k=2$ or $aba \leftrightarrow bab$ for $k=3?$

LATER Here is an elaboration in a more general context. It is essentially trivial as I give it here. The question is if it is useful for this problem.

Without being too specific about the setting (I'll suggest one below), fix $d,k$ and let $\mathcal{N}=\mathcal{N}_{d,k}$ be the family of (labelled) $(d,k)$-nice digraphs. This is a (rather) special subfamily of $\mathcal{D}=\mathcal{D}_{d,k}$ the family of digraphs with $d^k$ vertices each of indegree=outdegree=$d.$

For $G,H \in \mathcal{D}$ there is some $\ell \geq 2$ such that $G$ has $\ell$ edges not in $H$ and $H$ has $\ell$ edges not in $G.$ We can change $G$ into $H$ by a single $\ell$-"switch." Call a $2$-switch simply a switch. This means replacing two edges shown in red with two shown in blue or vice versa.

enter image description here

We can create a graph whose vertices are labelled by the members of $\mathcal{D}$ with an edge between pairs which can be obtained by a switch. This graph is connected.

But what use is all this for $\mathcal{N}?$ We can certainly move around in $\mathcal{N}$ using $\ell$-switches of various sizes $\ell$. The question is if we can do so with $2$-switches or maybe $d-1$-switches?

SETTING: Here is one possibility. Since we are interested in $\mathcal{N}$ and the appropriate De Bruijn graph seems very distinguished, let's start there. Let's always label the vertices with length $k$ words over a $d$-letter alphabet. Since there are exactly $d$ vertices with loops, label them with the constant words.

So that is a start: Perhaps consider only digraphs with $d^k$ vertices each of indegree=outdegree=$d$ labelled by the words of length $k$ in $\{0,1,\cdots,d-1\}$ Having exactly $d$ loops which occur at the vertices labelled by constant words. Consider only $\ell$ switches which do not create or destroy loops.

Further regularities could be required. The unique walk of length $k$ between two of those now labelled points must actually be the shortest path between them (any shorter path can be augmented to a walk in several ways by loops at the start or end.) Do these $d(d-1)$ paths necessarily need to be internally disjoint? I want to say yes, but I'm not sure. If so, then, as in the De Bruijn graph, we can decree that the labels on the $d(d-1)(d-2)$ internal points are labeled with the words of the form $xx\cdots xyy\cdots y.$ And, again if this is true, we could consider those edges unswitchable.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks, for your answer, well spotted! I'll think about it more, I wonder if we can obtain all the $(d,k)$ nice graphs from this kind of switching, and if there is a way to characterize all legal switches. $\endgroup$
    – Antoine Labelle
    Commented Jul 19, 2020 at 16:16
  • $\begingroup$ Hum, I think that this switching operation only works for $k=2$, at least if we start from a de Bruijn graph. Indeed, for the operation to preserve niceness, we need the successors of $q_1,q_2$ to be the same and the predecessors of $p_1,p_2$ to be the same. In a de Bruijn graph, it means that $q_1,q_2$ differ only by their first letter, and $p_1,p_2$ by their last. But if $k>2$, then $p_1,p_2$ have the same second letter, which is the first letter of $q_1,q_2$, thus $q_1=q_2$ (so the switching switches nothing). $\endgroup$
    – Antoine Labelle
    Commented Jul 19, 2020 at 19:59
  • $\begingroup$ In the $k=2$ case, we must have $p_1,p_2=ab_1,ab_2$ and $q_1,q_2=b_1c,b_2c$ for some letters $a,b_1,b_2,c$ with $b_1\ne b_2$. The isomorphism class of the resulting graph depends on whether some of these four letters are equal. It would be interesting to find for each $d$ the number of non isomorphic graphs that we can obtain by this operation (it is clearly bounded by the number of possible relations of equality/non equality between the four letters) $\endgroup$
    – Antoine Labelle
    Commented Jul 19, 2020 at 20:14
  • $\begingroup$ For the $(4,3)$ De Bruijn graph , It works to switch edges $ (001,011),(002,021)$ to $(001,021),(002,021)$ It also works to switch $ (001,011),(002,021),(003,031)$ to $ (001,021),(002,031),(003,011).$ $\endgroup$
    – Aaron Meyerowitz
    Commented Jul 20, 2020 at 8:59

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .