Isoperimetric Numbers of Randomly Perturbed Intersection Graphs

Shang, Yilun (2019) Isoperimetric Numbers of Randomly Perturbed Intersection Graphs. Symmetry, 11 (4). ISSN 2073-8994

Preview

Text (Full text) Shang - Isoperimetric Numbers of Randomly Perturbed Intersection Graphs OA.pdf - Published Version Available under License Creative Commons Attribution 4.0. Download (304kB) | Preview

Abstract

Social networks describe social interactions between people, which are often modeled by intersection graphs. In this paper, we propose an intersection graph model that is induced by adding a sparse random bipartite graph to a given bipartite graph. Under some mild conditions, we show that the vertex–isoperimetric number and the edge–isoperimetric number of the randomly perturbed intersection graph on n vertices are Ω(1/lnn) asymptomatically almost surely. Numerical simulations for small graphs extracted from two real-world social networks, namely, the board interlocking network and the scientific collaboration network, were performed. It was revealed that the effect of increasing isoperimetric numbers (i.e., expansion properties) on randomly perturbed intersection graphs is presumably independent of the order of the network.

Actions (login required)

View Item

Downloads