Bounding The Number of Sets
Moon & Moser (1965) showed that any graph with n vertices has at most 3n/3 maximal cliques. Complementarily, any graph with n vertices also has at most 3n/3 maximal independent sets. A graph with exactly 3n/3 maximal independent sets is easy to construct: simply take the disjoint union of n/3 triangle graphs. Any maximal independent set in this graph is formed by choosing one vertex from each triangle. The complementary graph, with exactly 3n/3 maximal cliques, is a special type of Turán graph; because of their connection with Moon and Moser's bound, these graphs are also sometimes called Moon-Moser graphs. Tighter bounds are possible if one limits the size of the maximal independent sets: the number of maximal independent sets of size k in any n-vertex graph is at most
The graphs achieving this bound are again Turán graphs.
Certain families of graphs may, however, have much more restrictive bounds on the numbers of maximal independent sets or maximal cliques. For instance, if all graphs in a family of graphs have O(n) edges, and the family is closed under subgraphs, then all maximal cliques have constant size and there can be at most linearly many maximal cliques.
Any maximal-clique irreducible graph, clearly, has at most as many maximal cliques as it has edges. A tighter bound is possible for interval graphs, and more generally chordal graphs: in these graphs there can be at most n maximal cliques.
The number of maximal independent sets in n-vertex cycle graphs is given by the Perrin numbers, and the number of maximal independent sets in n-vertex path graphs is given by the Padovan sequence. Therefore, both numbers are proportional to powers of 1.324718, the plastic number.
Read more about this topic: Maximal Independent Set
Famous quotes containing the words bounding, number and/or sets:
“I fell her finger light
Laid pausefully upon life’s headlong train;—
The foot less prompt to meet the morning dew,
The heart less bounding at emotion new,
And hope, once crush’d, less quick to spring again.”
—Matthew Arnold (1822–1888)
“Ah, but to play man number one,
To drive the dagger in his heart,
To lay his brain upon the board
And pick the acrid colors out,
To nail his thought across the door,
Its wings spread wide to rain and snow,
To strike his living hi and ho....”
—Wallace Stevens (1879–1955)
“In my dealing with my child, my Latin and Greek, my accomplishments and my money stead me nothing; but as much soul as I have avails. If I am wilful, he sets his will against mine, one for one, and leaves me, if I please, the degradation of beating him by my superiority of strength. But if I renounce my will, and act for the soul, setting that up as umpire between us two, out of his young eyes looks the same soul; he reveres and loves with me.”
—Ralph Waldo Emerson (1803–1882)