O'Reilly logo

Analysis of Complex Networks by Frank Emmert-Streib, Matthias Dehmer

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

13.1 Introduction

Probably most mathematicians know the following formulas:

images

and

images

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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required