Clique coverings and partitions of line graphs
Resource
Discrete Mathematics 308 (11): 2075-2079
Journal
Discrete Mathematics
Journal Volume
308
Journal Issue
11
Pages
2075-2079
Date Issued
2008
Author(s)
Abstract
A clique in a graph G is a complete subgraph of G. A clique covering (partition) of G is a collection C of cliques such that each edge of G occurs in at least (exactly) one clique in C. The clique covering (partition) numbercc (G) (cp (G)) of G is the minimum size of a clique covering (partition) of G. This paper gives alternative proofs, using a unified approach, for the results on the clique covering (partition) numbers of line graphs obtained by McGuinness and Rees [On the number of distinct minimal clique partitions and clique covers of a line graph, Discrete Math. 83 (1990) 49-62]. We also employ the proof techniques to give an alternative proof for the De Brujin-Erdo{combining double acute accent}s Theorem. © 2007 Elsevier B.V. All rights reserved.
Type
journal article
File(s)![Thumbnail Image]()
Loading...
Name
04.pdf
Size
24.16 KB
Format
Adobe PDF
Checksum
(MD5):ae0929251c69a182b9808f1989c2bcb7