Timeline for Digraphs with unique walk of length $k$ between any two vertices
Current License: CC BY-SA 4.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 20, 2020 at 8:59 | comment | added | Aaron Meyerowitz | 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).$ | |
| Jul 20, 2020 at 7:26 | history | edited | Aaron Meyerowitz | CC BY-SA 4.0 |
added 2523 characters in body
|
| Jul 19, 2020 at 20:14 | comment | added | Antoine Labelle | 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) | |
| Jul 19, 2020 at 19:59 | comment | added | Antoine Labelle | 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). | |
| Jul 19, 2020 at 16:16 | comment | added | Antoine Labelle | 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. | |
| Jul 19, 2020 at 10:06 | history | answered | Aaron Meyerowitz | CC BY-SA 4.0 |