Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
You could use "disjoint union of stars". Also "star forest" sounds fine, as long as you define the term before using it. –  Yuval Filmus Dec 22 '11 at 22:25
    
@Yuval: I think you can post your comment as answer. –  Paul Dec 23 '11 at 0:17
add comment

3 Answers

up vote 2 down vote accepted

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

What about galaxy?

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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