1
$\begingroup$

I'm wondering if there is a name for graphs such that if there is an edge between vertices A and B and a second edge between vertices B and C then there must be an edge between vertices A and C. My understanding is that this means that the graph is composed entirely of cliques. The graph need not be connected so it may contain multiple cliques, but there cannot be any edges between cliques.

Is there a particular name for this structure?

Thanks!

$\endgroup$
  • 3
    $\begingroup$ Basically a graph whose connected components are complete graphs? $\endgroup$ – Seth Jan 8 '15 at 21:34
  • 2
    $\begingroup$ A multiclique. $\endgroup$ – Théophile Jan 8 '15 at 21:36
  • 2
    $\begingroup$ A transitive graph. If you want, an equivalence relation. $\endgroup$ – Mariano Suárez-Álvarez Jan 8 '15 at 21:49
2
$\begingroup$

As suggested in the comments, you could say

A disjoint union of complete graphs

or

A graph whose connected components are complete

These graphs are also precisely the graphs whose edges induce an equivalence relation. So rather than study $G$ as a graph, you could study it as a set with an equivalence relation:

Let $G$ be a set with an equivalence relation $\sim$.

This of course assumes that $G$ has no loops, and $a \sim a$ is understood for all $a \in G$.

If $G$ is directed, then the property is a little more interesting; in this case what you have is basically a set with a preorder:

Let $G$ be a set and let $\le$ be a preorder on $G$.

In summary:

  • A directed graph can be understood as a set with a binary relation;

  • An undirected graph (allowing loops) can be understood as a directed graph whose binary relation is symmetric;

  • A undirected graph where loops are not allowed can be understood as a directed graph whose binary relation is symmetric and reflexive;

  • Your property is equivalent to the relation also being transitive.

$\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.