JISE


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


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


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

  Retrieve PDF document (JISE_200402_01.pdf)