General results on tolerance intersection graphs

From MaRDI portal





Let \(\mu\) be a function that assigns to each subset \(S\) of a set \(X\) a positive real number \(\mu(S)\), and let \(V\) be a finite set and \(S_ i\) a subset of \(X\) for all \(v_ i\in V\). Then a tolerance function assigns to each \(S_ i\) a positive real number \(t_ i\). Furthermore let \(\Phi\) be a function that assigns a positive real number to each pair of positive reals. By applying both these functions \(\mu\) and \(\Phi\) Jacobson, McMorris and Mulder defined: A finite graph \(G=(V,E)\) is a \(\Phi\)- tolerance intersection graph iff every vertex \(v_ i\in V\) can be assigned a set \(S_ i\) and a tolerance \(t_ i\) so that \(v_ iv_ j\in E\) iff \(\mu(S_ i\cap S_ j)\geq\Phi(t_ i,t_ j)\). In the special case where \(\Phi\) is the constant function \(p\) and \(\mu\) is the size of the set \(S_ i\), \(G\) is called a \(p\)-intersection graph. (In the case that every \(v_ i\) is assigned an interval \(J_ i\) and \(\mu(J_ i)\) is the length of this interval, \(G\) is called a \(\Phi\)- tolerance interval graph.) In the present paper are stated the following general results about such graphs: Every graph is a \(\Phi\)-tolerance intersection graph for any \(\Phi\) (Proposition 1), and this also means that every graph is a \(p\)- intersection graph for any \(p\). All trees are \(\Phi\)-tolerance interval graphs for monotone increasing functions \(\Phi\) (Theorem 3). Almost all graphs are not \(\Phi\)-tolerance interval graphs for any polynomial function \(\Phi\) (Theorem 4). A generalization of results from Erdős- Goodman-Posa which are related to the so-called \(p\)-intersection number of \(G\) and which are given by an inequality depending on \(p\) and the number \(n\) of vertices (Proposition 2).











This page was built for publication: General results on tolerance intersection graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3984466)