A Graph Theoretical Analysis of the Number of Edges in k-dense Graphs

preprint2015arXivOpen access

Abstract

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 sub-graph) detection within a network/graph, we focused on finding characterizations of k-dense communities. For each edge uv∈E(G)uv\in E(G), the {\bf edge multiplicity} of uvuv in GG is given by mG(uv)=∣NG(u)∩NG(v)∣.m_G(uv)=|N_{G}(u)\cap N_{G}(v)|. For an integer kk with k≥2k\ge 2, a {\bf kk-dense community} of a graph GG, denoted by DCk(G)DC_k(G), is a maximal connected subgraph of GG induced by the vertex set $$V_{DC_k(G)} = \{v\in V(G) : \exists u\in V(G)\ {\rm such\ that\} uv\in E(G)\ {\rm and\} m_{DC_{k(G)}}(uv)\ge k-2\}.$$ In this research, we characterize which graphs are kk-dense but not (k+1)(k+1)-dense for some values of kk and study the minimum and maximum number of edges such graphs can have. A better understanding of kk-dense sub-graphs (or communities) helps in the study of the connectivity of large complex graphs (or networks) in the real world.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.