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)
“Take away from the courts, if it could be taken away, the power to issue injunctions in labor disputes, and it would create a privileged class among the laborers and save the lawless among their number from a most needful remedy available to all men for the protection of their business interests against unlawful invasion.... The secondary boycott is an instrument of tyranny, and ought not to be made legitimate.”
—William Howard Taft (1857–1930)
“To me this world is all one continued vision of fancy or imagination, and I feel flattered when I am told so. What is it sets Homer, Virgil and Milton in so high a rank of art? Why is Bible more entertaining and instructive than any other book? Is it not because they are addressed to the imagination, which is spiritual sensation, and but mediately to the understanding or reason?”
—William Blake (1757–1827)