What’s in a name?

I had an interesting interaction on Twitter today. I’m doing some research with a student that involves a little graph theory. We needed some graph theory terminology that I was sure was well-known (but not known to us), so I turned to Twitter.

Let $v$ be a vertex of directed graph. Define $A(v)$ to be the set of all vertices that point to $v$ and $B(v)$ to be the set of all vertices that $v$ points to.

For example, in the graph below $A(1)=\{11\}$ and $B(1)=\{3, 4, 11\}$ .

My question was: what do we call the sets $A(v)$ and $B(v)$ ?

I received quite a few replies, and quickly discovered that there is no standard terminology. Here’s what I heard:

$A(v)$	$B(v)$
inset	outset
parents	children
predecessors	successors
incoming vertices	outgoing vertices
preset	postset
in-neighbors	out-neighbors
backward star	forward star

(Alasdair McAndrew (@amca01) suggested I come up with my own terminology and gave some creative suggestions of his own.)

While I thought there would be one answer, I guess it isn’t too surprising that there isn’t—we can’t even decide on basic terminology: graph/network, vertex/node, etc. There are many places in mathematics in which there are multiple names or symbols for the same mathematical object. Just think of all the ways to write the derivative: $df/dx$ , $Df$ , $f'$ , and $\dot{f}$ (and calculus is much older than graph theory). Even multiplication can be expressed in multiple ways: $ab$ , $a\times b$ , $a\cdot b$ and $a*b$ .

Maybe we should institute a mathematical standards board…. nah!

5 Comments

Matt Leifer says:

June 10, 2010 at 1:44 pm

The parents/children terminology is common when dealing with directed acyclic graphs. I just assumed the terminology was also used for general directed graphs, but I could be wrong. I like it because it is suggests a whole range of other family-tree terminology, e.g. descendants for all vertices reachable by a path from a given vertex or cousins for connected (ignoring direction) vertices not reachable by a path. In directed acyclic graphs, it makes sense because you cannot have a parent that is also a child, or indeed a descendant that is also an ancestor. Indeed, a general directed acyclic graph is just a family tree for a species with a variable number of genders.

pat balew says:

June 11, 2010 at 2:09 am

I was just this morning reading an old(1924) article by Florian Cajori, “The Unification of Mathematical Notations in the Light of History”. Early on he suggests, “The admonition of History is clearly that the chance, haphazard proceedure of the past will NOT lead to uniformity.” I think the same can be said, perhaps more so, for terminology than notation.
In the end, his quote from Kipling may be the most apt
“There are nine and sixty ways
Of constructing tribal lays
And every single one of them is right.”

Clara says:

June 11, 2010 at 7:09 am

May the set’s names have changed? I think first column names are for B(v) and second column names are for A(v)