A Property About Minimum Edge- and Minimum Clique-Cover of a Graph |
| |
Authors: | Raffaele Mosca |
| |
Affiliation: | (1) Dipartimento di Matematica Pura e Applicata, Università degli Studi di L'Aquila, via Vetoio-67010 Coppito (L'Aquila), Italia, IT |
| |
Abstract: | Let G be a graph with n vertices, and denote as γ(G) (as θ(G)) the cardinality of a minimum edge cover (of a minimum clique cover) of G. Let E (let C) be the edge-vertex (the clique-vertex) incidence matrix of G; write then P(E)={x∈ℜ n :Ex≤1,x≥0}, P(C)={x∈ℜ n :Cx≤1,x≥0}, α E (G)=max{1 T x subject to x∈P(E)}, and α C (G)= max{1 T x subject to x∈P(C)}. In this paper we prove that if α E (G)=α C (G), then γ(G)=θ(G). Received: May 20, 1998?Final version received: April 12, 1999 |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|