Monophonic number of Kneser graphs and strongly 2-monophonic graphs
Boštjan Brešar, María Gracia Cornet, Tanja Dravec · 2025
Read Monophonic number of Kneser graphs and strongly 2-monophonic graphs by Boštjan Brešar, María Gracia Cornet, Tanja Dravec (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-18784.txt.
Introduction
A monophonic set in a graph is a set of vertices such that every vertex lies on some chord-free path between two of them. Boštjan Brešar, María Gracia Cornet, and Tanja Dravec pin down that number for Kneser graphs in this 2025 paper. Kneser graphs link sets that share no elements. The monophonic number is the size of the smallest such set.
The team establishes that number for all Kneser graphs in the valid range. For larger parameters, they prove a stronger fact: any two non-adjacent vertices already form a monophonic set. Graphs with that trait are called strongly 2-monophonic. They give conditions for the trait and show it survives taking products of graphs. Every Johnson graph has it, as do non-complete Hamming graphs. Chordal graphs, with one family of exceptions, do not. The paper maps a tidy corner of graph theory.
Catalog record
| CREATOR | Boštjan Brešar, María Gracia Cornet, Tanja Dravec |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 58 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-18784
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Monophonic number of Kneser graphs and strongly 2-monophonic graphs Boštjan Brešar, María Gracia Cornet, Tanja Dravec Abstract Given a graph G G a set S ⊂ V ( G ) S\subset V(G) is called monophonic if every vertex in G G lies on some induced path between two vertices in S S . The monophonic number, m ( G ) m(G) , of G G , which is the smallest cardinality of a monophonic set in G G , has been studied from various perspectives. In this paper, we establish m ( K ( n , r ) ) m(K(n,r)) for all Kneser graphs K ( n , r ) K(n,r) , where n ≥ 2 r n\geq 2r . In addition, when r ≥ 3 r\geq 3 , we prove an even stronger property, notably that every pair of non-adjacent vertices in K ( n , r ) K(n,r) forms a monophonic set. We call the graphs satisfying this property strongly 2 2 -monophonic graphs. We present several (sufficient and necessary) conditions for a graph to be strongly 2 2 -monophonic, and prove that the Cartesian product of any two strongly 2 2 -monophonic graphs is also such. Besides non-complete Hamming graphs, we also prove that every Johnson graph is strongly 2 2 -monophonic, whereas chordal graphs, with the exception of the graphs K n − e K_{n}-e , do not enjoy this property. Keywords : monophonic convexity, monophonic number, Kneser graphs, Johnson graphs, Cartesian product AMS subject classification (2010) : 05C69, 05C12, 05C76, 05D05 1 Introduction Over time, significant progress in graph theory has produced and examined numerous classes of graphs. Notably, many of these are connected to classical combinatorial structures with a fundamental example of the generalized Johnson graphs. Formally, given n\geq r , for each i\in\{0,\dots,r\} , the generalized Johnson graph J(n,r,i) is the graph whose vertices are all the r -element subsets of a fixed n -element set, and two vertices A and B are adjacent iff |A\cap B|=i . The cases i=0 and i=r-1 are the widely-known classes of the Kneser graph K(n,r) and the classical Johnson graph J(n,r) , respectively. The interest for Kneser graphs goes back to 1960s and 1970s when two classical theorems concerning their independence and chromatic number were proved [ 12 , 16 ] . Many other graph invariants have been investigated in Kneser graphs, which makes them one of the most intensively studied classes of graphs. A family \mathcal{C} of subsets of a finite set X is a convexity on X if \varnothing,X\in{\mathcal{C}} and \mathcal{C} is closed under intersections [ 24 ] . For an interval function I:X\times X\to 2^{X} a set S is convex if I(x,y)\subseteq S for any x,y\in S . In the context of graphs, the most prominent instance of interval function is given by the geodesic interval, I_{G}(u,v) , which by definition contains all vertices that lie on a shortest path between the vertices u and v in a graph G . The geodetic closure of S\subset V(G) , is defined as I_{G}\left[S\right]=\bigcup_{\{x,y\}\subset S}{I_{G}(x,y)} , and a set S of vertices in G is a geodetic set in G if I_{G}\left[S\right]=V(G) . The geodetic number , g(G) , of a graph G , is the minimum cardinality of a geodetic set in G . Besides the geodesic intervals, which are built from shortest paths, the monophonic intervals arising from induced paths have also been intensively studied; see [ 5 ] for a survey on various types of interval functions in discrete structures. Monophonic convexity (known also under the names induced path convexity and minimal path convexity) was considered already by Duchet [ 11 ] and Farber and Jamison [ 13 ] in the 1980s. In this context, given a graph G and u,v\in V(G) , by J_{G}(u,v) we denote the monophonic interval between u and v , which is the set of all vertices that lie on some induced u,v -path in G . A set of vertices S\subseteq V(G) is a monophonic set in G , if for every u\in V(G) there exist x,y\in S such that u\in J_{G}(x,y) . The monophonic number , m(G) , of G is the smallest cardinality of a monophonic set in G . The monophonic hull number of G is the smallest cardinality of a set S\subset V(G) such that no proper subset of V(G) that contains S is monophonically convex. Geodetic sets and geodesic convexity were studied from various aspects and in numerous classes of graphs; see three comprehensive surveys [ 4 , 6 , 21 ] . It was shown in [ 2 ] that the determination of g(G) is NP-hard. Moreover, it was proved in [ 9 ] that it is NP-complete to decide for a given chordal or chordal bipartite graph G and a given integer k , whether G has a geodetic set of cardinality at most k . Recently, the geodetic number was investigated in Kneser graphs [ 3 ] . For Kneser graphs of diameter 2, the exact values of both the geodetic number and the geodetic hull number were determined, while for Kneser graphs of larger diameter, upper bounds for these parameters were established. Concerning the computational complexity issues, there is an interesting discrepancy: there is a polynomial-time algorithm that computes the monophonic hull number of an arbitrary graph, while the determination of m(G) is NP-hard [ 10 ] ; see also [ 7 ] for a continuation of these studies. Hernando et al. [ 15 ] investigated relations between Steiner, geodetic and monophonic hull sets, Paluga and Canoy [ 20 ] studied the monophonic number under the operations of join and lexicographic product, while in [ 19 , 22 ] monophonic number and monophonic hull number in Cartesian products of graphs were investigated. Recently, the monophonic numbers and monophonic hull numbers of complementary prisms over arbitrary graphs were studied in [ 17 ] , while in [ 14 ] monophonic numbers of corona products of graphs were investigated. In this paper, we fill the gap in the literature by studying the monophonic number in Kneser graphs. We determine the exact values of monophonic numbers in all Kneser graph, and prove an even stronger property for a Kneser graph K(n,r) , where r\geq 3 , that every pair of non-adjacent vertices in K(n,r) is a monophonic set. We find this property quite fascinating and call the graphs that satisfy it strongly 2 -monophonic graphs. We prove that several other classes of graphs (such as Johnson graphs and non-complete Hamming graph) are strongly 2 -monophonic, and that some other classes of graphs (such as chordal graphs) have almost no graph with this property. The paper is organized as follows. In the remainder of this section we provide some basic definitions and notation, while Section 2 is devoted to our main results concerning the monophonic sets in Kneser graphs. As mentioned earlier m(K(n,r))=2 when r\geq 3 , while m(K(n,2))=3 . In the proof we combine a careful selection of (induced) paths with the monotonicity of the function m in Kneser graphs which states that m(K(n,r)) is non-increasing with increasing n . Section 3 is