Balanced and 1-balanced graph constructions
详细信息 查看全文
- 作者：Arthur M. Hobbs ; Lavanya Kannan ; Hong-Jian Lai ; Hongyuan Lai ; Guoqing Weng
- 关键词：Balanced graphs ; 1-balanced graphs ; Cartesian product of graphs ; Web graphs
- 刊名：Discrete Applied Mathematics
- 出版年：2010
- 出版时间：28 July 2010
- 年：2010
- 卷：158
- 期：14
- 页码：1511-1523
- 全文大小：356 K
文摘
There are several density functions for graphs which have found use in various applications. In this paper, we examine two of them, the first being given by b(G)=E(G)/V(G), and the other being given by g(G)=E(G)/(V(G)−ω(G)), where ω(G) denotes the number of components of G. Graphs for which b(H)≤b(G) for all subgraphs H of G are called balanced graphs, and graphs for which g(H)≤g(G) for all subgraphs H of G are called 1-balanced graphs (also sometimes called strongly balanced or uniformly dense in the literature). Although the functions b and g are very similar, they distinguish classes of graphs sufficiently differently that b(G) is useful in studying random graphs, g(G) has been useful in designing networks with reduced vulnerability to attack and in studying the World Wide Web, and a similar function is useful in the study of rigidity. First we give a new characterization of balanced graphs. Then we introduce a graph construction which generalizes the Cartesian product of graphs to produce what we call a generalized Cartesian product. We show that generalized Cartesian product derived from a tree and 1-balanced graphs are 1-balanced, and we use this to prove that the generalized Cartesian products derived from 1-balanced graphs are 1-balanced.