On Intersection Representations and Clique Partitions of Graphs

arXiv0804.4617MaRDI QIDQ6209319FDOQ6209319

Authors: Tao-Ming Wang, Jun-Lin Kuo 

Publication date: 29 April 2008

Abstract: A multifamily set representation of a finite simple graph $G$ is a multifamily $mathcalF$ of sets (not necessarily distinct) for which each set represents a vertex in $G$ and two sets in $mathcalF$ intersects if and only if the two corresponding vertices are adjacent. For a graph $G$, an extit{edge clique covering} ( extit{edge clique partition}, respectively) $mathcalQ$ is a set of cliques for which every edge is contained in extit{at least} ( extit{exactly}, respectively) one member of $mathcalQ$. In 1966, P. Erd"{o}s, A. Goodman, and L. P'{o}sa (The representation of a graph by set intersections, extit{Canadian J. Math.}, extbf{18}, pp.106-112) pointed out that for a graph there is a one-to-one correspondence between multifamily set representations $mathcalF$ and clique coverings $mathcalQ$ for the edge set. Furthermore, for a graph one may similarly have a one-to-one correspondence between particular multifamily set representations with intersection size at most one and clique partitions of the edge set. In 1990, S. McGuinness and R. Rees (On the number of distinct minimal clique partitions and clique covers of a line graph, extit{Discrete Math.} extbf{83} (1990) 49-62.) calculated the number of distinct clique partitions for line graphs. In this paper, we study the set representations of graphs corresponding to edge clique partitions in various senses, namely family representations of extit{distinct} sets, antichain representations of extit{mutually exclusive} sets, and uniform representations of sets with the extit{same cardinality}. Among others, we completely determine the number of distinct family representations and the number of antichain representations of line graphs.

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph representations (geometric and intersection representations, etc.) (05C62) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

This page was built for publication: On Intersection Representations and Clique Partitions of Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6209319)