A graph theoretical analysis of the number of edges in k-dense graphs
Loading...
Authors
Gera, Ralucca
Eroh, Linda
Escuadro, Henry
Prahlow, Samuel
Schmitt, Karl
Subjects
k-dense subnetworks
k-dense subgraph
k-dense community
k-dense graph
k-core subnetwork
k-dense subgraph
k-dense community
k-dense graph
k-core subnetwork
Advisors
Date of Issue
2016
Date
2016
Publisher
Language
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), the edge multiplicity of uv in G is given by
m(G)(uv) = |N(G)(u) ∩ N(G)(v)|. For an integer k with k ≥2, a k-dense community of a graph G,
denoted by DC(k)(G), is a maximal connected subgraph of G induced by the vertex set
V(DC(k))(G) = {v ϵ V (G) : Ǝu ϵ V (G) such that uv ϵ E(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.
Type
Article
Description
The article of record as published may be found at http://dx.doi.org/10.5614/ejgta.2016.4.1.4
Series/Report No
Department
Applied Mathematics
Organization
Naval Postgraduate School (U.S.)
Identifiers
NPS Report Number
Sponsors
Funder
Format
16 p.
Citation
Eroh, Linda, et al. "A graph theoretical analysis of the number of edges in k-dense graphs." Electronic Journal of Graph Theory and Applications (EJGTA) 4.1 (2016): 26-41.
Distribution Statement
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.