A Shy Invariant of Graphs |
| |
Authors: | Raffaele Mosca |
| |
Affiliation: | (1) via Latina 7, Pescara 65121, Italy. e-mail: ciufolini@tiscalinet.it, IT |
| |
Abstract: | Moving from a well known result of Hammer, Hansen, and Simeone, we introduce a new graph invariant, say λ(G) referring to any graph G. It is a non-negative integer which is non-zero whenever G contains particular induced odd cycles or, equivalently, admits a particular minimum clique-partition. We show that λ(G) can be efficiently evaluated and that its determination allows one to reduce the hard problem of computing a minimum clique-cover of a graph to an identical problem of smaller size and special structure. Furthermore, one has α(G)≤θ(G)−λ(G), where α(G) and θ(G) respectively denote the cardinality of a maximum stable set of G and of a minimum clique-partition of G. Received: April 12, 1999 Final version received: September 15, 2000 |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|