Timeline for Showing two vertices have same degree under a certain condition
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 7, 2020 at 14:33 | comment | added | Chris Godsil | @Ugly Duckling: If you want to discuss this further, you can find my email address by googling. | |
| Sep 7, 2020 at 1:43 | comment | added | Ugly Duckling | I think the answer is that trivially when there is an automorphism all properties of the vertex, including $P$, are carried over to its image. Then, other properties like (strong) regularity may play a role. I was also thinking of studying the distance matrices of these graphs to see if they have something in common... | |
| Sep 7, 2020 at 1:30 | comment | added | Ugly Duckling | That's bad news. I was guided by the path graph, for which $P_i=P_{n-i+1}$, and of course this is consistent with the action of the path-reversing $\sigma$. Also, $P$ is constant over the symmetric cycle graph, and for every non-central vertex of the wheel or star graphs. However I saw that it fails for Frucht graphs, which are $3-$regular but asymmetric, and yet $P$ is constant. Could it actually just be a sufficient, but not necessary condition? | |
| Sep 6, 2020 at 22:55 | comment | added | Chris Godsil | That will fail. Choose your graph to be strongly regular and asymmetric. | |
| Sep 6, 2020 at 15:22 | comment | added | Ugly Duckling | I'm thinking of a more general version of the problem. Right now we have found a necessary condition for $P_i=P_j$, but I have reasons to conjecture that $P_i=P_j$ if and only if there exists $\sigma\in\text{Aut}(G)$ such that $\sigma(v_i)=v_j$ (which of course implies the two vertices have the same degree). I'm open to ideas for a proof... but of course not a complete answer! | |
| Sep 6, 2020 at 12:03 | vote | accept | Ugly Duckling | ||
| Sep 6, 2020 at 12:02 | comment | added | Ugly Duckling | Thank you very much, Chris. Your answer is pretty close to what I was building up to: the big difference is that I was trying to calculate directly $(L-E_j)^k$ (I got stuck there and even asked another question here). I missed the idea of taking the time derivative! [I am an undergraduate physicist doing some research in quantum computation theory, the problem comes from there :)] | |
| Sep 6, 2020 at 3:01 | history | answered | Chris Godsil | CC BY-SA 4.0 |