I have different simple triangle graphs. As an instance, $G_1=(V_1,E_1)=(\{1,2,3\},\{\{1,2\},\{2,3\},\{3,1\}\})$ and $G_2=(V_2,E_2)=(\{1,4,5\},\{\{1,4\},\{4,5\},\{5,1\}\})$.

The union of both graphs is $H=(V_1 \cup V_2, E_1 \cup E_2)=(\{1,2,3,4,5\},\{\{1,2\},\{2,3\},\{3,1\},\{1,4\},\{4,5\},\{5,1\}\})$

Does a graph like $H$ that results from the union of triangles have a particular name or properties?

  • $\begingroup$ are these graphs or hypergraphs? Is {1,2,3} an edge? What is {{1,2},{2,3},{3,1}}? $\endgroup$
    – kodlu
    Oct 15 at 23:55
  • $\begingroup$ Hello @kodlu. I added more details to the question. $\endgroup$ Oct 16 at 5:29
  • 1
    $\begingroup$ (i) You are looking for a name for the graph property "the graph can be expressed as a union of triangles", right? (ii) By union, do you mean disjoint union as in your example? Or just regular union? $\endgroup$
    – Neal Young
    Oct 22 at 17:54
  • 1
    $\begingroup$ Your example shows that a vertex could belong to two (or more?) triangles, but it is not clear if you are allowing edges to belong to two (or more) triangles as well. Since you ask for a name OR a property, perhaps a characterizing property would be "a graph where every vertex and every edge is in a triangle". $\endgroup$
    – JimN
    Oct 27 at 11:58
  • 1
    $\begingroup$ As a bigger picture, if you are just dealing with triplets and trying to analyze how they interact with each other, then consider the possibility that a graph data structure is not an ideal way to look at them. You should probably be looking at sets-of-3set structures, or block designs. For example, if you have triangles abd, bce, acf and you form your graph, then the graph would have four triangles (abd, bce, acf and also triangle abc) while your initial set of triplets was three 3sets. $\endgroup$
    – JimN
    Oct 27 at 12:08

According to Wikipedia, this graph is known variously as the butterfly graph, bowtie graph, or hourglass graph.

  • 5
    $\begingroup$ With the caveat that the butterfly/bowtie/hourglass graph is just one particular graph. It is not a general name for any graph that can be formed as the union of triangles. $\endgroup$
    – Neal Young
    Oct 22 at 17:53
  • 2
    $\begingroup$ Ah, indeed. I was only looking at the graph $H$ from the question. I think the OP would need to provide some more examples where there are >2 triangles in the union in order to see more clearly what family of graphs are under consideration (E.g.: are all of the triangles joined only at one common vertex or are there other ways of joining them?) $\endgroup$
    – mhum
    Oct 22 at 19:30

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.