publication . Preprint . 2012

The groupies of random multipartite graphs

Portmann, Marius; Wang, Hongyun;
Open Access English
  • Published: 14 Sep 2012
Abstract
If a vertex $v$ in a graph $G$ has degree larger than the average of the degrees of its neighbors, we call it a groupie in $G$. In the current work, we study the behavior of groupie in random multipartite graphs with the link probability between sets of nodes fixed. Our results extend the previous ones on random (bipartite) graphs.
Subjects
arXiv: Computer Science::Discrete Mathematics
ACM Computing Classification System: MathematicsofComputing_DISCRETEMATHEMATICS
free text keywords: Mathematics - Combinatorics, Mathematics - Probability, 05C07, 05C80
Related Organizations
Download from

[1] C. C. Aggarwal, H. Wang, A survey of clustering algorithms for graph data. Advances in Database Systems, 40(2010) pp.275-301

[2] E. Bertram, P. Erd˝os, P. Hora´k, J. Sˇir´anˇ, Zs. Tuza, Local and global average degree in graphs and multigraphs. Journal of Graph Theory, 18(1994) pp.647-661

[3] W. Fernandez de la Vega, Zs. Tuza, Groupies in random graphs. Information Processing Letters, 109(2009) pp.339-340

[4] S. Janson, T. Luczak, A. Rucinski, Random Graphs. Wiley, New York, 2000

[5] J. Mackey, A lower bound for groupies in graphs. Journal of Graph Theory, 21(1996) pp.323-326

[6] Y. Shang, Groupies in random bipartite graphs. Applicable Analysis and Discrete Mathematics, 4(2010) pp.278-283

Powered by OpenAIRE Open Research Graph
Any information missing or wrong?Report an Issue