2
$\begingroup$

Let $G=(V,E)$ be an directed graph such that the following condition holds. If $(a,b)\in E$ then there exists $c\in V\setminus \{a,b\}$ such that $(a,c)\in E$ and $(c,b)\in E$.

Question: Was this type of graphs investigated? Does this type of graphs have a name?

$\endgroup$
5
  • $\begingroup$ what is "ordered graph"? $\endgroup$ – Dima Pasechnik Dec 2 '19 at 13:10
  • $\begingroup$ do you mean "directed graph", a.k.a. "digraph" ? $\endgroup$ – Dima Pasechnik Dec 2 '19 at 13:12
  • $\begingroup$ Yes, i was wrong. $\endgroup$ – Markiian Khylynskyi Dec 2 '19 at 13:14
  • 3
    $\begingroup$ Googling "every edge belongs to a triangle" reveals that this property has been discussed several times, but there is no special term for it. Since your directed version of this property is more special, I expect there is no standard term for it either ... $\endgroup$ – Nik Weaver Dec 2 '19 at 15:23
  • $\begingroup$ @NikWeaver thanks! $\endgroup$ – Markiian Khylynskyi Dec 2 '19 at 18:53
2
$\begingroup$

For undirected graphs, this seems similar to the Friendship Graph--a graph in which, if two vertices are "friends" (i.e. share an edge), then they have exactly one common friend (i.e. exactly one new vertex that is adjacent to both of them). You don't seem to require the "exactly one" part of this definition, but looking into the Friendship Graph might help you find some related results.

$\endgroup$

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.