Description

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:

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.

Reuse Permissions
  • 590.83 KB application/pdf

    Download count: 0

    Details

    Contributors
    Date Created
    • 2011
    Resource Type
  • Text
  • Collections this item is in
    Note
    • Partial requirement for: Ph.D., Arizona State University, 2011
      Note type
      thesis
    • Includes bibliographical references (p. 155-158)
      Note type
      bibliography
    • Field of study: Mathematics

    Citation and reuse

    Statement of Responsibility

    by Louis DeBiasio

    Machine-readable links