Previous | [ 1] | [ 2] | [ 3] | [ 4] | [ 5] | [ 6] | [ 7] | [ 8] | [ 9] | [ 10] |

¡@

in Graph

**Ton Kloks ^{**}, Chuan Min Lee and Jiping Liu^{**+}**

The University of Lethbridge

Alberta, T1K 3M4, Canada

E-mail: {kloks, liu}@cs.uleth.ca

Department of Computer Science and Information Engineering

National Chung Cheng University

Chiayi, 621 Taiwan

E-mail: cmlee@cs.ccu.edu.tw

In this paper we study the edge-thickness and the clique-thickness of a graph. The edge-thickness of a graph is defined as the thickness of the family of edges. The clique-thickness of a graph is defined as the thickness of the family of maximal cliques. Edges and maximal cliques of a graph are both considered as a collection of subsets of the vertex set. On one hand, we introduce a new parameter called stickiness. We show the relation between stickiness and edge-thickness, and show how the stickiness of a graph can be computed in a more efficient way. On the other hand, we show that the clique-thickness is equal to the reciprocal of the fractional stability number. For graphs having the property that the clique cover number is equal to the independence number it follows that the clique-thickness is equal to the reciprocal of the independence number, and in this case it is computable in polynomial time.

*
Keywords:
*
thickness, edge-thickness, clique-thickness, stickiness, fractional stability number, clique cover number, independence number

Retrieve PDF document (**200403_01.pdf**)

Received January 31, 2003; accepted July 4, 2003.

Communicated by Ruay-Shiung Chang.
^{*}A preliminary version of this paper has been presented at the 2002 International Computer Symposium: Workshop on Algorithms and Computational Molecular Biology (partially supported by Ministry of Education and the National Science council of the R.O.C.), Hualien, Taiwan, R.O.C.
^{+}Partially supported by NSERC of Canada.