𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the number of distinct minimal clique partitions and clique covers of a line graph

✍ Scribed by Sean McGuinness; Rolf Rees

Publisher
Elsevier Science
Year
1990
Tongue
English
Weight
812 KB
Volume
83
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

Let G be a line graph. Orlin determined the clique covering and clique partition numbers cc(G) and cp(G). We obtain a constructive proof of Orlin's result and in doing so we are able to completely enumerate the number of distinct minimal clique covers and partitions of G, in terms of easily calculable parameters of G. We apply our results to give a new proof of Whitney's Theorem:

if G and H are graphs, neither of which is K,, then G and H are isomorphic if and only if their line graphs are isomorphic.

πŸ“œ SIMILAR VOLUMES

On the partition and coloring of a graph
On the partition and coloring of a graph by cliques
✍ W.D. Wallis; Guo-Hui Zhang πŸ“‚ Article πŸ“… 1993 πŸ› Elsevier Science 🌐 English βš– 859 KB

Wallis, W.D. and G.-H. Zhang, On the partition and coloring of a graph by cliques, Discrete Mathematics 120 (1993) 191-203. We first introduce the concept of the k-chromatic index of a graph, and then discuss some of its properties. A characterization of the clique partition number of the graph G V

An upper bound on the size of a largest
An upper bound on the size of a largest clique in a graph
✍ Dennis P. Geoffroy; David P. Sumner πŸ“‚ Article πŸ“… 1978 πŸ› John Wiley and Sons 🌐 English βš– 308 KB πŸ‘ 1 views

## Abstract A graph is point determining if distinct vertices have distinct neighborhoods. The nucleus of a point‐determining graph is the set __G__^O^ of all vertices, __v__, such that __G__–__v__ is point determining. In this paper we show that the size, Ο‰(__G__), of a maximum clique in __G__ sat