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)
“The growing good of the world is partly dependent on unhistoric acts; and that things are not so ill with you and me as they might have been, is half owing to the number who lived faithfully a hidden life, and rest in unvisited tombs.”
—George Eliot [Mary Ann (or Marian)
“Nothing sets a person up more than having something turn out just the way it’s supposed to be, like falling into a Swiss snowdrift and seeing a big dog come up with a little cask of brandy round its neck.”
—Claud Cockburn (1904–1981)