A Note on Threshold Dimension of Permutation Graphs

MaRDI QIDQ6214231zbMATH OpenFDO

Authors Diptendu Bhowmick

Publication date 5 June 2009

Abstract: A graph $G(V,E)$ is a threshold graph if there exist non-negative reals $w_v,vinV$ and $t$ such that for every $UsubseteqV$, $su{m}_{vinU}{w}_{v}leqt$ if and only if $U$ is a stable set. The {it threshold dimension} of a graph $G(V,E)$, denoted as $t(G)$, is the smallest integer $k$ such that $E$ can be covered by $k$ threshold spanning subgraphs of $G$. A permutation graph is a graph that can be represented as the intersection graph of a family of line segments that connect two parallel lines in the Euclidean plane. In this paper we will show that if $G$ is a permutation graph then $t(G)leqalpha(G)$ (where $alpha(G)$ is the cardinality of maximum independent set in $G$) and this bound is tight. As a corollary we will show that $t(G)leqfracn2$ where $n$ is the number of vertices in the permutation graph $G$. This bound is also tight.

This page was built for publication: A Note on Threshold Dimension of Permutation Graphs

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