2
$\begingroup$

A tree is a special kind a graph.

However, I came across a data structure which is a like a rooted tree, but where nodes are authorized to have direct links to any of their descendants. Shortcuts if you will.

This is not a tree anymore.

This is a specialized DAG that has more restriction. That is, it has a single root (or source)

Does this type of graph have a name?

CLARIFICATION:

By 'tree', I'm referring to the tree data structure, not a tree in graph theory. It seems crazy to me that such related objects have the same name even though they don't mean the same thing. The tree data structure is always rooted but there are rooted DAG that are not trees.

{1→2, 2→3, 1→3, 4→2} doesn't qualify because 4→2 is an edge toward an ancestor, not a descendant. {1→2, 1→3, 2→4, 3→4} doesn't qualify.

{1→2, 2→3, 1→3} and {1→2, 1→3, 2→4, 3→5, 3→6, 1→4, 1→6} both qualify.

$\endgroup$
  • $\begingroup$ Let $G$ be the graph on $\{1, 2, 3, 4\}$ and edges $\{1\to2,\ 2\to3,\ 1\to3,\ 4\to2\}$. Is $G$ an example of the graphs you are talking about? Note that $G$ has two sources (or roots). $\endgroup$ – Apass.Jack Aug 21 '18 at 18:23
  • 2
    $\begingroup$ Possible duplicate of What do you call a DAG with a single root/source? $\endgroup$ – Pål GD Aug 21 '18 at 19:56
  • $\begingroup$ @PålGD No, it's more restrictive than a single-sourced DAG and this isn't a duplicate. The graph shown in the question you've linked is not in the class Clement is interested in. $\endgroup$ – David Richerby Aug 21 '18 at 22:12
  • $\begingroup$ @Apass.Jack, I clarified the question. G doesn't qualify because of 4→2. $\endgroup$ – Clement Aug 21 '18 at 23:46
  • $\begingroup$ OK, I am glad you have clarified you are talking tree data structure. However, it looks like you have conflicting description when you said "which is a like a rooted tree, but where nodes are authorized to have direct links to any of their descendants" and that you believe "{1→2, 1→3, 2→4, 3→4} " qualifies. Please check my answer. $\endgroup$ – Apass.Jack Aug 22 '18 at 0:26
3
$\begingroup$

This answer does not have a suggestion as to what existing names we might have. Rather, it is about what names are not appropriate.

To be clear, the OP talks about a graph that is a rooted tree with possibly extra edges from some nodes to its descendants. Let us call this kind of graph "Clement directed acycle graph" or, in short, "Clement DAG" for the lack of a better concise name (Clement is the OP's username).

The simplest example of Clement DAG that is not a tree is a graph on vertices $\{1,2,3\}$ with edges $\{1\to 2,\ 2\to 3,\ 1\to 3\}$.

One might be tempted to think "a Clement DAG" is none other than "a rooted directed acycle graph"(rooted DAG) or, what is equivalent, "a directed acyclic graph with a single source". Indeed, a Clement DAG is always a rooted DAG. However, a rooted DAG is not necessarily a Clement DAG! Here is an example given by David Richerby. Let $G$ be a graph vertices $\{1,2,3,4\}$ with edges $\{1\to 2,\ 1\to 3,\ 2\to 4,\ 3\to 4\}$. $G$ has a single root, $1$. If $G$ is a Clement DAG, $G$ must be a tree since it has no extra edge that connects any node to its descendants others than its children. However, $G$ has a cycle.

$\endgroup$
  • $\begingroup$ So I guess there is no official name for it yet. I hope that "Clement DAG" sticks :) $\endgroup$ – Clement Aug 22 '18 at 23:05
3
$\begingroup$

I'm not aware of any standard term. The graphs that you describe are subgraphs of the transitive closure of a tree, if that's of any help to you, but one wouldn't want to use that phrase twenty times in a paper.

But... as Pål GD alludes to in a comment, every DAG on $n$ vertices is a subgraph of the transitive closure of the $n$-vertex directed path. So this answer is a bit of a fail, really.

$\endgroup$
  • $\begingroup$ Then again ... every graph is (isomorphic to) a subgraph of a transitive closure of a tree. $\endgroup$ – Pål GD Aug 22 '18 at 15:46
  • $\begingroup$ @PålGD Well, "directed" was strongly implicit... so it's only every DAG. But, still, oops. $\endgroup$ – David Richerby Aug 22 '18 at 15:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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