In a large network (graph) it would be desirable to guarantee the existence of some local property based only on global knowledge of the network. Consider the following classical example: how many connections are necessary to guarantee that the network contains three nodes which are pairwise adjacent? It turns out that more than n^2/4 connections are needed, and no smaller number will suffice in general.
Download count: 0
- Partial requirement for: Ph.D., Arizona State University, 2011Note typethesis
- Includes bibliographical references (p. 155-158)Note typebibliography
- Field of study: Mathematics