6
$\begingroup$

I am asked to find the join of two graphs in graph theory. But I cannot find the exact definition! I know that in lattice theory, we join every vertex of a graph to every vertex of another graph to find the join of graphs. Any expert advice is welcome.

$\endgroup$
2
  • $\begingroup$ perhaps providing the actual question would be helpful. Literally, the join is the "graph with all the edges that connect the vertices of the first graph with the vertices of the second graph." $\endgroup$ Mar 10, 2016 at 2:13
  • $\begingroup$ Let me know that when we draw join of two graphs, is that I should join every vertex of graph1 to every vertex of graph 2 by an edge? $\endgroup$ Mar 10, 2016 at 2:22

3 Answers 3

4
$\begingroup$

The join of two graphs $G_1$ and $G_2$ , denoted by $G_1\nabla G_2 $, is a graph obtained from $G_1$ and $G_2$ by joining each vertex of $G_1$ to all vertices of $G_2$ . After joining the two graph the resultant graph will be of diameter at most 2.

$\endgroup$
2
  • 2
    $\begingroup$ Note that the symbol for graph join is not standard. Different notations used also include $G_1+G_2$ (i don't like notation at all + is more commonly used for disjoint union), and $G_1\vee G_2$. $\endgroup$ Jan 27, 2020 at 10:28
  • $\begingroup$ I have seen $G*H$ too, for the join of two graphs. $\endgroup$ Apr 27, 2023 at 14:43
3
$\begingroup$

Join of two graphs $G_1=(V_1, E_1)$ and $G_2=(V_2, E_2)$ is mathematically denoted and defined as $G_1\nabla G_2=(V_1\cup V_2, E_1\cup E_2\cup\lbrace (a, b): a\in V_1, b\in V_2\rbrace)$

Note that in this process, self loops will be generated if $ G_1$ and $G_2$ contain atleast one common vertex and multiple edges may arise if $ G_1$ and $G_2$ contain atleast two common vertices or so. The following is an example of graph join:

enter image description here

$\endgroup$
1
$\begingroup$

A more Computer Science oriented solution: https://arxiv.org/pdf/1608.05594.pdf

$\endgroup$

You must log in to answer this question.

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