EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Sparse Graphs With Local Covering Conditions on Edges

Debsoumya Chakraborti, Amirali Madani, Anil Maheshwari, Babak Miraftab

Journal of Graph Theory · 07.07.2026

DOI: 10.1002/jgt.70096 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Journal of Graph Theory, online erschienen am 07.07.2026. Verfasst von Debsoumya Chakraborti und 3 weiteren Autor:innen. Die Arbeit nennt 19 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

In 1988, Erdős suggested the question of minimizing the number of edges in a connected ‐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 ” for . 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 triangles for instead of only one triangle. We completely resolve this problem for with the characterization of all extremal graphs.

Zitieren

APA

Chakraborti, D., Madani, A., Maheshwari, A., & Miraftab, B. (2026). Sparse Graphs With Local Covering Conditions on Edges. Journal of Graph Theory. https://doi.org/10.1002/jgt.70096

Vancouver

Chakraborti D, Madani A, Maheshwari A, Miraftab B. Sparse Graphs With Local Covering Conditions on Edges. Journal of Graph Theory. 2026. doi:10.1002/jgt.70096

BibTeX
@article{Chakraborti2026,
  author = {Chakraborti, Debsoumya and Madani, Amirali and Maheshwari, Anil and Miraftab, Babak},
  title = {Sparse Graphs With Local Covering Conditions on Edges},
  journal = {Journal of Graph Theory},
  year = {2026},
  doi = {10.1002/jgt.70096}
}
Kostenlos starten →