On generalized windmill graphs

In this paper we will consider generalizations of the class of so-called windmill graphs, which were recently introduced by Estrada [6]. A windmill graph W(η,k) consists of η copies of the complete graph Kk, with every node connected to a common node. Estrada [6] showed that the clustering coefficient and the transitivity index of windmill graphs diverge, when the graph size tends to infinity. In addition [6] studied the spectra of the adjacency and the Laplacian matrices of these graphs. In this paper we will generalize the family of windmill graphs in three ways. We will study properties for all three types of generalized windmill graphs. In particular we will focus on the behavior of the two clustering metrics. We will quantify the difference between the two metrics, under various conditions. In addition, we give the spectra of the adjacency and the Laplacian matrices of these graphs. We will also derive analytic expressions for several other graph metrics, such as average path length, heterogeneity index and a variety of robustness metrics. We also show how the generalized windmill graphs can be used to construct pairs of non-isomorphic graphs with the same number of nodes and links. Finally, we will show how generalized windmill graphs occur quite naturally in the study of public transportation networks.