A graph theoretical analysis of the number of edges in k-dense graphs

Download
Author
Gera, Ralucca
Eroh, Linda
Escuadro, Henry
Prahlow, Samuel
Schmitt, Karl
Date
2016Metadata
Show full item recordAbstract
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.
Description
The article of record as published may be found at http://dx.doi.org/10.5614/ejgta.2016.4.1.4
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.Collections
Related items
Showing items related by title, author, creator and subject.
-
STRUCTURAL PROPERTIES OF I-GRAPHS: THEIR INDEPENDENCE NUMBERS AND CAYLEY GRAPHS
Klein, Zachary J. (Monterey, CA; Naval Postgraduate School, 2020-06);We discuss in this paper the independence numbers and algebraic properties of I-graphs. The I-graphs are a further generalization of the Generalized Petersen graphs whose independence numbers have been previously researched. ... -
On the hardness of recognizing triangular line graphs
Anand, Pranav; Escuadro, Henry; Gera, Ralucca; Hartke, Stephen G.; Stolee, Derrick (2010);Given a graph G, its triangular line graph is the graph T(G) with vertex set consisting of the edges of G and adjacencies between edges that are incident in G as well as being within a common triangle. Graphs with a ... -
A characterization of graphs with interval two-step graphs
Merz, Sarah K.; Rasmussen, Craig W.; Lundgren, J. Richard; Maybee, John Stanley (Monterey, California. Naval Postgraduate School, 1993); NPS-MA-93-021One of the intriguing open problems on competition graphs is determining what digraphs have interval competition graphs. In this paper we consider this problem for the class of loopless symmetric digraphs. Here we first ...