A graph theoretical analysis of the number of edges in k-dense graphs - Linda Eroh; Henry Escuadro; Ralucca Gera; Samuel Prahlow; Karl Schmitt (GTA Research Group, Univ. Newcastle, Indonesian Combinatorics Society and ITB, 2016)
Due to the increasing discovery and implementation of networks within all disciplines of life, the study of subgraph connectivity has become increasingly important. Motivated by the idea of community (or subgraph) detection within a network/graph, we focused on finding characterizations of k-dense communities. For each edge uvE(G), the edge multiplicity of uv in G is given by m_G(uv)=|N_G(u)N_G(v)|. For an integer k with k2, a k-dense community of a graph G, denoted by DC_k(G), is a maximal connected subgraph of G induced by the vertex setV_DC_k(G) = {vV(G) : uV(G) such that uvE(G) and m_DC_k(G)(uv)k-2}.In this research, we characterize which graphs are k-dense but not (k+1)-dense for some values of k and study the minimum and maximum number of edges such graphs can have. A better understanding of k-dense sub-graphs (or communities) helps in the study of the connectivity of large complex graphs (or networks) in the real world.