Analysis of Complex Networks

13.8 Summary and Conclusion

In this chapter we have surveyed almost all, to the best of our knowledge, known results on counting hypercubes in median graphs and related problems. Among special families of median graphs, other related families of graphs with interesting metric properties were also discussed, that is, quasi median graphs, cage-amalgamation graphs, and partial cubes. The basic notions and tools from metric graph theory were presented in the first part. All known treelike equalities and Euler-type inequalities were collected. The properties of cube and Hamming polynomials were treated and their applications to phylogenetics were mentioned. Naturally, many new questions will arise and new challenges will appear. We state some of the intriguing problems that seem promising.

Although the location of roots of cube polynomials of median graphs is quite well understood, it also seems interesting to consider the roots of Hamming polynomials.

It would be interesting to find more treelike equalities for graph classes whose members can be obtained by a sequence of amalgamations (of a special type) from families of graphs with special properties.

Perhaps one could generalize Euler-type inequalities of partial cubes to hold for partial Hamming graphs, or even more generally l₁-graphs?

And finally, for an arbitrary graph G what is the role of the canonical metric representation of G in counting special subgraphs induced by products of some factors appearing in the canonical metric ...