EUVIMEDEUVIMED entdecken
Crossref

Monophonic number of Kneser graphs and strongly 2-monophonic graphs

Boštjan Brešar, María Gracia Cornet, Tanja Dravec

Discrete Applied Mathematics · 2026-11 · 393 · 287-300

DOI: 10.1016/j.dam.2026.07.008 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Discrete Applied Mathematics, 2026-11. Verfasst von Boštjan Brešar und 2 weiteren Autor:innen. Die Arbeit nennt 25 Literaturangaben. Gefördert von: National Scientific and Technical Research Council, National University of Rosario, National Agency for the Promotion of Research Technological Development and Innovation.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Given a graph $G$ a set $S\subset V(G)$ is called monophonic if every vertex in $G$ lies on some induced path between two vertices in $S$. The monophonic number, $m(G)$, of $G$, which is the smallest cardinality of a monophonic set in $G$, has been studied from various perspectives. In this paper, we establish $m(K(n,r))$ for all Kneser graphs $K(n,r)$, where $n\ge 2r$. In addition, when $r\ge 3$, we prove an even stronger property, notably that every pair of non-adjacent vertices in $K(n,r)$ forms a monophonic set. We call the graphs satisfying this property strongly $2$-monophonic graphs. We present several (sufficient and necessary) conditions for a graph to be strongly $2$-monophonic, and prove that the Cartesian product of any two strongly $2$-monophonic graphs is also such. Besides non-complete Hamming graphs, we also prove that every Johnson graph is strongly $2$-monophonic, whereas chordal graphs, with the exception of the graphs $K_n-e$, do not enjoy this property.

Förderung

  • National Scientific and Technical Research Council
  • National University of Rosario
  • National Agency for the Promotion of Research Technological Development and Innovation
  • Slovenian Research and Innovation Agency

Zitieren

APA

Brešar, B., Cornet, M. G., & Dravec, T. (2026). Monophonic number of Kneser graphs and strongly 2-monophonic graphs. Discrete Applied Mathematics, 393, 287-300. https://doi.org/10.1016/j.dam.2026.07.008

Vancouver

Brešar B, Cornet MG, Dravec T. Monophonic number of Kneser graphs and strongly 2-monophonic graphs. Discrete Applied Mathematics. 2026;393:287-300. doi:10.1016/j.dam.2026.07.008

BibTeX
@article{Brear2026,
  author = {Brešar, Boštjan and Cornet, María Gracia and Dravec, Tanja},
  title = {Monophonic number of Kneser graphs and strongly 2-monophonic graphs},
  journal = {Discrete Applied Mathematics},
  year = {2026},
  volume = {393},
  pages = {287--300},
  doi = {10.1016/j.dam.2026.07.008}
}
Kostenlos starten →