# to clear doubt about basic definition in graph theory

Can anybody help me in clearing the doubt about hierarchical product of graphs. Its quite different from other graph products. Here is the screenshot and link how it is done. I know the rooted graph, but its applied here by using 0 in definition and in adjacency relation is out of my mind. I will be thankful if a little hint is provided. Thanks a lot.

http://www.sciencedirect.com/science/article/pii/S0166218X08001960

-

Simirairly to this answer, you can benefit by thinking about the components of the product as dimensions. The difference is, that in Cartesian product you could walk arbitrarily as long as the graph would allow, while here, if you want to move at "bigger" coordinates, then you need to go to $0$ (the designated vertex, here marked with the color of the graph) at "smaller" coordinates. I don't know what I could say more besides the definition, so I adapted the example from the other answer (be aware, here the order matters).

I hope this helps $\ddot\smile$

-
Fantastic diagrams- what did you use to make them? – Devlin Mallory Aug 7 '13 at 20:42
Inkscape and some simple scripting. – dtldarek Aug 7 '13 at 20:46
Thanks! I'll try it out- these look very nice. – Devlin Mallory Aug 7 '13 at 20:48
Can u clarify how the vertices are labelled as 00,01.... etc... this kind of labelling we see in hypercubes, but how here? – monalisa Aug 8 '13 at 3:33
@monalisa I've added some labels, not all because it wouldn't be readable, but I guess enough to know what's going on. Also, I was doing it by hand, so I might have made some mistakes, just let me know if something doesn't fit. – dtldarek Aug 8 '13 at 7:27

The hierarchical product of two graphs $A,B$ boils down to this: For each vertex in $B$ draw a small copy of $A$. Then, viewing these copies of $A$ as vertices connect these (represented by their root nodes) according to the edges in $B$.

Cf. the image of $K_2^3$: "Macroscopically" this is a $K_2$, an edge with two end points. If you "look closer" the end points themselves are copies of $K_2^2$, i.e. an edge between two vertices that - upon even closer inspection - turn out to be tiny $K_2$'s themselves.

-