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

DOI10.5614/EJGTA.2016.4.1.4MaRDI QIDQ5006573zbMATH OpenOpenAlexFDO

Authors

Publication date 16 August 2021

Published in Electronic Journal of Graph Theory and Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution-ShareAlike 4.0 International

Full work available at URL https://arxiv.org/abs/1505.04300

zbMATH Keywords

\(k\)-core\(k\)-core subnetwork\(k\)-dense community\(k\)-dense graph\(k\)-dense subnetworks (or \(k\)-dense subgraph)

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Structural characterization of families of graphs (05C75)

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 $uvinE(G)$, the {�f edge multiplicity} of $uv$ in $G$ is given by $m_G(uv)=|N_G(u)cap{N}_G(v)|.$ For an integer $k$ with $kge2$, a {�f $k$-dense community} of a graph $G$, denoted by $D{C}_k(G)$, is a maximal connected subgraph of $G$ induced by the vertex set ${\displaystyle }$V_{DC_k(G)} = {vin V(G) : exists uin V(G) { m such that} uvin E(G) { m and} m_{DC_{k(G)}}(uv)ge k-2}.${\displaystyle }$ 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.

Recommendations

• Finding densest \(k\)-connected subgraphs
• Finding Connected Dense k-Subgraphs
• Many disjoint dense subgraphs versus large \(k\)-connected subgraphs in large graphs with given edge density
• Determination of the densest subgraph
• Lower-bounds on the connectivities of a graph

Cites work

• Practical graph isomorphism. II.
• Reducibility among combinatorial problems

Cited in

(1)

• A generalization of a Turán's theorem about maximum clique on graphs

Describes a project that uses

Uses Software

• Traces
• SageMath
• nauty

This page was built for publication: A graph theoretical analysis of the number of edges in \(k\)-dense graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5006573)