On Greedy Clique Decompositions and Set Representations of Graphs

Details On Greedy Clique Decompositions and Set Representations of Graphs On Greedy Clique Decompositions and Set Representations of Graphs

2008-04-16

arxiv.org/abs/0804.2584v1

Mathematics

Combinatorics

15 pages, 3 figures

Scientific paper

In 1994 S. McGuinness showed that any greedy clique decompo- sition of an n-vertex graph has at most $\lfloor n^2/4 \rfloor$ cliques (The greedy clique decomposition of a graph, J. Graph Theory 18 (1994) 427-430), where a clique decomposition means a clique partition of the edge set and a greedy clique decomposition of a graph is obtained by removing maximal cliques from a graph one by one until the graph is empty. This result solved a conjecture by P. Winkler. A multifamily set rep- resentation of a simple graph G is a family of sets, not necessarily distinct, each member of which represents a vertex in G, and the in- tersection of two sets is non-empty if and only if two corresponding vertices in G are adjacent. It is well known that for a graph G, there is a one-to-one correspondence between multifamily set representations and clique coverings of the edge set. Further for a graph one may have a one-to-one correspondence between particular multifamily set rep- resentations with intersection size at most one and clique partitions of the edge set. In this paper, we study for an n-vertex graph the variant of the set representations using a family of distinct sets, including the greedy way to get the corresponding clique partition of the edge set of the graph. Similarly, in this case, we obtain a result that any greedy clique decomposition of an n-vertex graph has at most $\lfloor n^2/4 \rfloor$ cliques.

Affiliated with

Also associated with

No associations

Rating

On Greedy Clique Decompositions and Set Representations of Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On Greedy Clique Decompositions and Set Representations of Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Greedy Clique Decompositions and Set Representations of Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-607273