Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4949760 | Discrete Applied Mathematics | 2017 | 11 Pages |
Abstract
This paper studies the problem of finding graphs that locally maximize the clustering coefficient in the space of graphs with a fixed degree sequence. Such a graph is characterized by the property that the clustering coefficient cannot be increased, no matter how a single 2-switch is applied. First, an explicit formula for the amount of change in the clustering coefficient of a graph caused by a single 2-switch is given. Next, some classes of graphs with the property stated above are presented. An example of such a graph is the one obtained from a tree by replacing its edges with cliques with the same order.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Tatsuya Fukami, Norikazu Takahashi,