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?

Improve this question
$\endgroup$
6
  • $\begingroup$ what is "ordered graph"? $\endgroup$
    – Dima Pasechnik
    Commented Dec 2, 2019 at 13:10
  • $\begingroup$ do you mean "directed graph", a.k.a. "digraph" ? $\endgroup$
    – Dima Pasechnik
    Commented Dec 2, 2019 at 13:12
  • $\begingroup$ Yes, i was wrong. $\endgroup$
    – Markiian Khylynskyi
    Commented Dec 2, 2019 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
    Commented Dec 2, 2019 at 15:23
  • 1
    $\begingroup$ If the directed graph is transitive (and hence determines an order), then such order is usually called a dense order (en.wikipedia.org/wiki/Dense_order). By analogy such digraphs can be called "dense digraphs". On the other hand, a pair $(x,y)$ of elements of an ordered set with $x<y$ and $\{z:x<z<y\}=\emptyset$ is called a jump. So, digraphs with your property can be also called jumpless. If you look at the order topologies, then such topologies are called crowded, so those digraphs can be also called "crowded digraphs". $\endgroup$
    – Taras Banakh
    Commented Mar 11, 2023 at 16:23

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .