Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

enter image description here

enter image description here

share|cite|improve this question
up vote 3 down vote accepted

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$

share|cite|improve this answer
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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.