A Note on Threshold Dimension of Permutation Graphs - Mathematics > CombinatoricsReportar como inadecuado




A Note on Threshold Dimension of Permutation Graphs - Mathematics > Combinatorics - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

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.



Autor: Diptendu Bhowmick

Fuente: https://arxiv.org/







Documentos relacionados