Sparse graphs with local covering conditions on edges
Preprint
Abstract
In 1988, Erdős suggested the question of minimizing the number of edges in a connected $n$-vertex graph where every edge is contained in a triangle. Shortly after, Catlin, Grossman, Hobbs, and Lai resolved this in a stronger form. In this paper, we study a natural generalization of the question of Erdős in which we replace `triangle' with `clique of order $k$' for ${k\ge 3}$. We completely resolve this generalized question with the characterization of all extremal graphs. Motivated by applications in data science, we also study another generalization of the question of Erdős where every edge is required to be in at least $\ell$ triangles for $\ell\ge 2$ instead of only one triangle. We completely resolve this problem for $\ell = 2$.
Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- Building large k-cores from sparse graphsJournal of Computer and System Sciences, 2022
- Truss-based Community Search over Large Directed Graphs2020
- Cohesive Subgraph Search Using Keywords in Large NetworksIEEE Transactions on Knowledge and Data Engineering, 2020
- Extremal Graphs with Local Covering ConditionsSIAM Journal on Discrete Mathematics, 2020
- Discovering Maximal Motif Cliques in Large Heterogeneous Information Networks2019
- Exploring Communities in Large Profiled GraphsIEEE Transactions on Knowledge and Data Engineering, 2018
- Can We Create Large k-Cores by Adding Few Edges?2018
- Efficient and effective community searchData Mining and Knowledge Discovery, 2015
- Graph Twiddling in a MapReduce WorldComputing in Science & Engineering, 2009
- Fractional arboricity, strength, and principal partitions in graphs and matroidsDiscrete Applied Mathematics, 1992