First of all observe that if we have $G$, a $D$-regular graph over $N$ vertices that is equipped with a consistent labeling $\ell$ then we can induce a consistent labeling for $L(G)$ the line graph of $G$.

This is done in the following way, every edge $e$ in $G$ has a label $\ell(e)$.

Every edge $e'$ in $L(G)$ connects two adjacent edges $e_1,e_2$ in $G$, thus the new labeling for $L(G)$ can be $\ell'(e')=\ell(e_1)-\ell(e_2)\ (\text{mod}\ D)$.

It is not hard to verify that if $\ell$ is consistent then $\ell'$ is also consistent.

Now, how is the above fact that consistent labeling for $G$ induces a consistent labeling for $L(G)$ implies explicit $\text{UES}$.

More concretely, is it possible (using the above fact directly) to give a log-space algorithm that on input $1^{N+D}$ outputs a $\text{UES}$ for $D$-regular graphs over $N$ vertices.

Note: I am familiar with transitions from $\text{UTS}$ to $\text{UES}$, but I am more concerned about the connections with the line graph properties.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.