Show simple item record

dc.contributor.authorGera, Ralucca
dc.contributor.authorEroh, Linda
dc.contributor.authorEscuadro, Henry
dc.contributor.authorPrahlow, Samuel
dc.contributor.authorSchmitt, Karl
dc.date2016
dc.date.accessioned2016-07-27T17:15:52Z
dc.date.available2016-07-27T17:15:52Z
dc.date.issued2016
dc.identifier.citationEroh, 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.en_US
dc.identifier.urihttp://hdl.handle.net/10945/49288
dc.descriptionThe article of record as published may be found at http://dx.doi.org/10.5614/ejgta.2016.4.1.4en_US
dc.description.abstractDue 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.en_US
dc.format.extent16 p.en_US
dc.rightsThis 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.en_US
dc.titleA graph theoretical analysis of the number of edges in k-dense graphsen_US
dc.typeArticleen_US
dc.contributor.corporateNaval Postgraduate School (U.S.)en_US
dc.contributor.departmentApplied Mathematicsen_US
dc.subject.authork-dense subnetworksen_US
dc.subject.authork-dense subgraphen_US
dc.subject.authork-dense communityen_US
dc.subject.authork-dense graphen_US
dc.subject.authork-core subnetworken_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record