A Note on Threshold Dimension of Permutation Graphs - Mathematics > CombinatoricsReport as inadecuate




A Note on Threshold Dimension of Permutation Graphs - Mathematics > Combinatorics - Download this document for free, or read online. Document in PDF available to download.

Abstract: A graph $GV,E$ is a threshold graph if there exist non-negative reals $w v,v \in V$ and $t$ such that for every $U \subseteq V$, $\sum {v \in U} w v\leqt$ if and only if $U$ is a stable set. The {\it threshold dimension} of a graph$GV,E$, denoted as $tG$, is the smallest integer $k$ such that $E$ can becovered by $k$ threshold spanning subgraphs of $G$. A permutation graph is agraph that can be represented as the intersection graph of a family of linesegments that connect two parallel lines in the Euclidean plane. In this paperwe will show that if $G$ is a permutation graph then $tG \leq \alphaG$where $\alphaG$ is the cardinality of maximum independent set in $G$ andthis bound is tight. As a corollary we will show that $tG \leq \frac{n}{2}$where $n$ is the number of vertices in the permutation graph $G$. This bound isalso tight.



Author: Diptendu Bhowmick

Source: https://arxiv.org/



DOWNLOAD PDF




Related documents