2
$\begingroup$

I'm looking for a specific name for a bipartite graph $(U,V,E)$ in which there is at most one edge incident to each vertex $u \in U$. That is, $|E_u| \le 1$ for all $u \in U$, where $E_u = \{(u,v) \in E\}$.

The best I have been able to think of is "star forest", but this term seems to be used specifically for subgraphs.

It would be helpful if there was also terminology for the vertex sets $U$ (with maximal degree 1) and $V$ (with arbitrary degree).

Background: the application is in parallel computing where each vertex has a canonical owner, but may be "ghosted" in other memory spaces. Sometimes the term "local-to-global map" is used for this, but the concept is more general.

  • 0
    @Yuval: I think you can post your comment as answer.2011-12-23

3 Answers 3

2

You could use "disjoint union of stars". Also "star forest" sounds fine, as long as you define the term before using it.

0

I talked to a graph theorist friend who also affirmed that "star forest" is a good, unambiguous name. She pointed out that in the other instances where this term is used, the authors really meant spanning star forest. Here is a draft of some notes I'm writing on the communication model. An implementation in terms of MPI one-sided operations is in the development version of PETSc.

0

What about galaxy?

On the same rationalization that a forest is a disjoint union of trees.