A Problem on Clique Partitions of Regular Graphs

Article Details

Rigor B. Ponsones, nan, Mathematics Department, De La Salle University
Francis Joseph H. Campeña, , Mathematics Department, De La Salle University

Journal: Manila Journal of Science
Volume 11 Issue 2 (Published: 2018-01-01)

Abstract

A clique partition of a simple graph G is a collection of complete subgraphs of G (called cliques) that partitions the edge set of G. The cardinality of a minimum clique partition number of G is called the clique partition number of G and is denoted by cp(G). This paper presents some approaches in determining integers x for which a graph G on n vertices with clique partition number x exists.

Keywords: Clique Partition, Clique Partition Number, Regular Graph

DOI: https://www.dlsu.edu.ph/wp-content/uploads/pdf/research/journals/mjs/MJS11-2018/volume-2/MJS11-8-ponsones-et-al.pdf

References:

1] Bondy, J.A., & Murty, U.S.R., . (1977). Graph Theory with Applications. Great Britain: The MacMillian Press, 1977.

[2] Eades, P. et. a., l. (1984). On Clique Partition Numbers of Regular Graph. In Progress in Graph Theory, 1984, (pp. 191-–201). Canada: Academic Press.

[3] Erdős, P., Goodman, A.W., and & Pósa, L. (1966). The representation of a graph by set

intersections, . Can. adian Journal of Math. ematics, 18 (1966), 106-–112.

[4] Hall, Jr., M., Jr. (1941). A problem in partitions . Bull. etin of the Amer. ican Math. ematical Soc., iety, 47 (1941), 801-–807.

[5] Harary, F., . (1969). Graph Theory. Addison-Wesley Publishing Company 1969.

[6] Pullman, N.J., . (xxxx1983). Clique Coverings of Graphs-—A Survey. Lecture Notes in Mathematics, Combinatorial Mathematics, X10, Vol. 1036.

Cited by:

None...