Examples of products giving large graphs with given degree and diameter (Q1199421): Difference between revisions

Let \(G=(V_ 1,E_ 1)\) and \(H=(V_ 2,E_ 2)\) be finite undirected graphs, and let \(\varphi\) be an automorphism of \(H\). Let the edges of \(G\) be oriented in some way: let \(\vec E_ 1\) denote the set of ordered pairs which are the directed edges of the resulting directed graph. The product \(G*_ \varphi H\) is an undirected graph defined in terms of this orientation of \(G\). \[ V(G*_ \varphi H)=V(G)\times V(H); \] \[ E(G*_ \varphi H)=\bigl\{(g,h)(g,h'): hh'\in E_ 2\bigr\}\cup\bigl\{(g,h)(g',\varphi(h)): gg'\in\vec E_ 1\bigr\}. \] ``We can say that we build a product of \(G\) with a half of \(H\). (...) Of course, a change in the orientation of \(G\) modifies the resulting \(G*_ \varphi H\). (...) In the following most calculations will give an upper bound for the diameter that holds for any orientation in \(G\). Hence we do not recall the orientation in the notation \(*_ \varphi\).'' This product is applied to give some constructions giving large graphs with given degree and diameter.