Monophonic number of Kneser graphs and strongly 2-monophonic graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866915508810416128 |
|---|---|
| author | Brešar, Boštjan Cornet, María Gracia Dravec, Tanja |
| author_facet | Brešar, Boštjan Cornet, María Gracia Dravec, Tanja |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_18784 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Monophonic number of Kneser graphs and strongly 2-monophonic graphs Brešar, Boštjan Cornet, María Gracia Dravec, Tanja Combinatorics 05C69, 05C12, 05C76, 05D05 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. |
| title | Monophonic number of Kneser graphs and strongly 2-monophonic graphs |
| topic | Combinatorics 05C69, 05C12, 05C76, 05D05 |
| url | https://arxiv.org/abs/2509.18784 |