Exploring K-Dense Graphs Within Graph Theoretical Analysis

Faculty Sponsor

Karl Schmitt


Arts and Sciences



Document Type

Poster Presentation

Celebration Date

Summer 7-31-2014


Due to the increasing implementation and discovery of networks within all disciplines of life, the study of connectivity, specifically sub-graphs within these larger networks, has become increasingly important. Network theory has been helpful in cancer research, finding an efficient business model, and developing comprehensive security measures. Motivated by the idea of community (or sub-graph) detection within complex networks, we focused on finding characterizations of k-dense communities. We present some initial results about the equivalency between k-clique, k-dense, and k-core sub-graphs when the number of vertices equals the k value. Success by others in characterizing k-cliques and k-core led us to examine patterns in k-dense. We show several graphic progressions and tables which suggest potential formulas, and possible generalization to a minimum edge construction for any k-dense graph. Continuing this research has implications for being able to better understand and distinguish the k-dense sub-graphs, which in turn would help in the study of the connectivity and characterizations of the larger graph/network in the real world.

Biographical Information about Author(s)

Samuel Prahlow is a junior mathematics major at Valparaiso University. He became interested in Graph Theory during the spring semester of 2014, when he heard a lecture given by (his now research mentor) Dr. Karl Schmitt on "Open Questions within Complex Networks." He plans to continue working on this research with Professor Schmitt in the fall. While graph theoretical analysis research is his current focus, he hopes to get involved in bio-statistical research in the future. After completing his degree at VU, he plans on applying to a MeSH Program in order to attain an M.D. and a Ph.D.

This document is currently not available here.