1
$\begingroup$

Let $G=(V,E)$ be a graph. A 1-Lipschitz vertex projection is a map $p: E \to V$ such that $p(e)$ is always an end-vertex of $e$, and if $e,f$ have a common end-vertex, then $p(e)$ and $p(f)$ coincide or share an edge. The name is motivated by noticing that if we think of $G$ as an 1-complex, with each edge having length 1, and we think of $p$ as mapping midpoints of edges to $V$, then this map is 1-Lipschitz iff the aforementioned condition is satisfied.

Main Question Which graphs admit an 1-Lipschitz vertex projection?

It is easy to see that trees, cycles, and cliques do. Not every graph does (try e.g. piecing 4-cycles together).

Question 2: Does every chordal graph admit an 1-Lipschitz vertex projection?

$\endgroup$
2
  • $\begingroup$ Don't you mean that an edge should be mapped to its endpoint? Otherwise you can map everything to one vertex. $\endgroup$ Aug 30 at 12:20
  • $\begingroup$ Yes, sorry, I'm amending the question. $\endgroup$
    – Agelos
    Aug 30 at 13:09

1 Answer 1

2
$\begingroup$

I assume that $p$ should map each edge to one of its endpoints. Under this assumption, any vertex projection $p\colon E\to V$ corresponds to orientation of all edges (edge $e$ is oriented towards $p(e)$), and the 1-Lipschitz condition means that the out-neighbours of any vertex form a clique. So the existence of a 1-Lipschitz projection is equivalent to existence of such orientation.

In particular, if the graph is chordal, one can take a perfect elimination ordering of the vertices, and orient each edge towards the vertex with larger number, to get a desired orientation.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.