EUVIMEDEUVIMED entdecken
Open Access · CC BY-ND 4.0

New constructions of Meyniel extremal families of graphs

Anthony Bonato, Ryan Cushman, Trent G. Marbach

Contributions to Discrete Mathematics · 27.02.2026 · 21 (1) · 123-141

DOI: 10.55016/yyry5x69 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Contributions to Discrete Mathematics, online erschienen am 27.02.2026. Verfasst von Anthony Bonato und 2 weiteren Autor:innen. Der Volltext ist frei zugänglich (Open Access, CC BY-ND 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We provide new constructions of Meyniel extremal graphs, which are families of graphs with the conjectured largest asymptotic cop number. Using spanning subgraphs, we prove that there are an exponential number of new Meyniel extremal families with specified degrees. Using linear programming on hypergraphs, we explore the degrees in families that are not Meyniel extremal. We give the best-known upper bound on the cop number of vertex-transitive graphs with a prescribed degree. We find new Meyniel extremal families of regular graphs with large chromatic number, large diameter, and explore the connection between Meyniel extremal graphs and bipartite graphs. Conjectures relating Meyniel extremal families to maximum and average degrees in their graphs are presented.

Zitieren

APA

Bonato, A., Cushman, R., & Marbach, T. G. (2026). New constructions of Meyniel extremal families of graphs. Contributions to Discrete Mathematics, 21(1), 123-141. https://doi.org/10.55016/yyry5x69

Vancouver

Bonato A, Cushman R, Marbach TG. New constructions of Meyniel extremal families of graphs. Contributions to Discrete Mathematics. 2026;21(1):123-141. doi:10.55016/yyry5x69

BibTeX
@article{Bonato2026,
  author = {Bonato, Anthony and Cushman, Ryan and Marbach, Trent G.},
  title = {New constructions of Meyniel extremal families of graphs},
  journal = {Contributions to Discrete Mathematics},
  year = {2026},
  volume = {21},
  number = {1},
  pages = {123--141},
  doi = {10.55016/yyry5x69}
}
Kostenlos starten →