Mathematics – Combinatorics
Scientific paper
2009-06-05
Mathematics
Combinatorics
8 pages, 3 figures
Scientific paper
A graph $G(V,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\leq t$ 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) \leq \alpha(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) \leq \frac{n}{2}$ where $n$ is the number of vertices in the permutation graph $G$. This bound is also tight.
Bhowmick Diptendu
No associations
LandOfFree
A Note on Threshold Dimension of Permutation Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A Note on Threshold Dimension of Permutation Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Note on Threshold Dimension of Permutation Graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-522935