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$ Commented Aug 30, 2023 at 12:20
  • $\begingroup$ Yes, sorry, I'm amending the question. $\endgroup$
    – Agelos
    Commented Aug 30, 2023 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .