Monophonic number of Kneser graphs and strongly 2-monophonic graphs
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.
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}
}
EUVIMED