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

@

Journal of Information Science and Engineering, Vol. 20 No. 2, pp. 207-217 (March 2004)

Stickness, Edge-Thickness, and Clique-Thickness
in Graph
*

Ton Kloks**, Chuan Min Lee and Jiping Liu**+
**Department of Mathematics and Computer Science
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

Full Text () 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.