Timeline for Digraphs with unique walk of length $k$ between any two vertices
Current License: CC BY-SA 4.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 21, 2020 at 12:50 | comment | added | Antoine Labelle | No, as I said we can show that such a graoh necessarily have $d$ loops (the eigenvalues of $A$ are $0,0,\ldots,0,d$, so the trace is $d$, so there are $d$ loops) | |
| Jul 21, 2020 at 3:52 | comment | added | Brendan McKay | (I'll pose this as a question if there isn't an answer soon.) Both the de Bruijn digraphs and the extra digraph shown here have loops. Are there any examples without loops? | |
| Jul 20, 2020 at 14:16 | comment | added | Antoine Labelle | Yes, this includes from a vertex to itself | |
| Jul 20, 2020 at 12:34 | comment | added | Brendan McKay | By "between any two vertices" you include "from a vertex to itself", right? | |
| Jul 19, 2020 at 19:35 | history | edited | Antoine Labelle | CC BY-SA 4.0 |
edited title
|
| Jul 19, 2020 at 16:18 | history | edited | Antoine Labelle | CC BY-SA 4.0 |
edited body
|
| Jul 19, 2020 at 16:10 | comment | added | Antoine Labelle | 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 | |
| Jul 19, 2020 at 10:34 | comment | added | M. Winter | 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"? | |
| Jul 19, 2020 at 10:06 | answer | added | Aaron Meyerowitz | timeline score: 2 | |
| Jul 18, 2020 at 3:12 | comment | added | Richard Stanley | 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$. | |
| Jul 18, 2020 at 1:44 | comment | added | Antoine Labelle | 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? | |
| Jul 18, 2020 at 0:11 | comment | added | Richard Stanley | 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. | |
| S Jul 17, 2020 at 16:18 | history | suggested | RobPratt | CC BY-SA 4.0 |
corrected spelling in title
|
| Jul 17, 2020 at 16:17 | review | Suggested edits | |||
| S Jul 17, 2020 at 16:18 | |||||
| Jul 17, 2020 at 16:15 | history | asked | Antoine Labelle | CC BY-SA 4.0 |