Analysis of Complex Networks

13.1 Introduction

Probably most mathematicians know the following formulas:

and

The first formula is a characteristic property of trees, where n and m denote the number of vertices and number of edges, respectively. The second formula is Euler's formula for planar graphs, where, in addition to the same meaning of n and m, f denotes the number of faces of a planar graph. In this chapter we present different equalities and inequalities of a similar nature for a special class of bipartite graphs, with rich structural properties, that allow one to count their special subgraphs. These graphs are called median graphs, and hypercubes can be considered in some special way as their building blocks. Therefore, the number of different hypercubes of given dimensions can be regarded also as a measure of complexity for median graphs. To count induced (maximal) hypercubes in median graphs is as hard a problem as counting complete graphs in arbitrary graphs. However, many nice theoretical results have been obtained and applications found. The most interesting is the application of counting hypercubes in phylogenetic analysis; in particular it has been used to detect phantom mutations in sequenced mitochondrial DNA data.

The chapter is organized as follows. In Section 13.2 some basic notions from ...