The maximum number of maximal independent sets in unicyclic connected graphs

In this paper, we determine the maximum number of maximal independent sets in a unicyclic connected graph. We also find a class of graphs achieving this maximum value.     

Constraints on the number of maximal independent sets in graphs

A maximal independent set of a graph G is an independent set that is not contained properly in any other independent set of G. Let i(G) denote the number of maximal independent sets of G. Here, we prove two conjectures, suggested by P. Erdös, that the maximum number of maximal independent sets among all graphs of order n in a family Φ is o(3^n/3) if Φ is either a family of connected graphs such that the largest value of maximum degrees among all graphs of order n in Φ is o(n) or a family of graphs such that the approaches infinity as n → ∞.     

The number of independent sets in graphs

The following theorem is proved: Let G be a κ-regular graph with n vertices such that the maximal size of an independent set of the graph G is equal to μ. Then i(G) ≤ \(2^{\mu \log } (1 + \tfrac{n}{{2\mu }}) + O(n\sqrt {k^{ - 1} \log k} )\). This statement is generalized to the case of quasi-regular graphs. As a corollary, an upper bound for the number of independent sets in extenders is obtained.     

Polar graphs and maximal independent sets

We study two central problems of algorithmic graph theory: finding maximum and minimum maximal independent sets. Both problems are known to be NP-hard in general. Moreover, they remain NP-hard in many special classes of graphs. For instance, the problem of finding minimum maximal independent sets has been recently proven to be NP-hard in the class of so-called (1,2)-polar graphs. On the other hand, both problems can be solved in polynomial time for (1,1)-polar, also known as split graphs. In this paper, we address the question of distinguishing new classes of graphs admitting polynomial-time solutions for the two problems in question. To this end, we extend the hierarchy of (α,β)-polar graphs and study the computational complexity of the problems on polar graphs of special types.     

On maximal independent sets of vertices in claw-free graphs

A graph is claw-free if: whenever three (distinct) vertices are joined to a single vertex, those three vertices are a nonindependent (nonstable) set. Given a finite claw-free graph with real numbers (weights) assigned to the vertices, we exhibit an algorithm for producing an independent set of vertices of maximum total weight. This algorithm is “efficient” in the sense of J. Edmonds, that is to say, the number of computational steps required is of polynomial (not exponential or factorial) order in n, the number of vertices of the graph. This problem was solved earlier by Edmonds for the special case of “edge-graphs”; our solution is by reducing the more general problem to the earlier-solved special case. Separate attention is given to the case in which all weights are (+1) and thus an independent set is sought which is maximal in the sense of its cardinality.     

Counting the number of independent sets in chordal graphs

We study some counting and enumeration problems for chordal graphs, especially concerning independent sets. We first provide the following efficient algorithms for a chordal graph: (1) a linear-time algorithm for counting the number of independent sets; (2) a linear-time algorithm for counting the number of maximum independent sets; (3) a polynomial-time algorithm for counting the number of independent sets of a fixed size. With similar ideas, we show that enumeration (namely, listing) of the independent sets, the maximum independent sets, and the independent sets of a fixed size in a chordal graph can be done in constant time per output. On the other hand, we prove that the following problems for a chordal graph are #P-complete: (1) counting the number of maximal independent sets; (2) counting the number of minimum maximal independent sets. With similar ideas, we also show that finding a minimum weighted maximal independent set in a chordal graph is NP-hard, and even hard to approximate.     

Fast algorithms for identifying maximal common connected sets of interval graphs

Given a family of interval graphs F={G₁=(V,E₁),…,G_k=(V,E_k)} on the same vertices V, a set S⊂V is a maximal common connected set of F if the subgraphs of G_i,1?i?k, induced by S are connected in all G_i and S is maximal for the inclusion order. The maximal general common connected set for interval graphs problem (gen-CCPI) consists in efficiently computing the partition of V in maximal common connected sets of F. This problem has many practical applications, notably in computational biology. Let n=|V| and . For k?2, an algorithm in O((kn+m)logn) time is presented in Habib et al. [Maximal common connected sets of interval graphs, in: Combinatorial Pattern Matching (CPM), Lecture Notes in Computer Science, vol. 3109, Springer, Berlin, 2004, pp. 359-372]. In this paper, we improve this bound to O(knlogn+m). Moreover, if the interval graphs are given as k sets of n intervals, which is often the case in bioinformatics, we present a simple time algorithm.     

Disjoint cliques and disjoint maximal independent sets of vertices in graphs

In this paper, we find lower bounds for the maximum and minimum numbers of cliques in maximal sets of pairwise disjoint cliques in a graph. By complementation, these yield lower bounds for the maximum and minimum numbers of independent sets in maximal sets of pairwise disjoint maximal independent sets of vertices in a graph. In the latter context, we show by examples that one of our bounds is best possible.     

Extending the Balas-Yu bounds on the number of maximal independent sets in graphs to hypergraphs and lattices

A result of Balas and Yu (1989) states that the number of maximal independent sets of a graph G is at most ^p+1, where is the number of pairs of vertices in G at distance 2, and p is the cardinality of a maximum induced matching in G. In this paper, we give an analogue of this result for hypergraphs and, more generally, for subsets of vectors in the product of n lattices =₁××_n, where the notion of an induced matching in G is replaced by a certain binary tree each internal node of which is mapped into . We show that our bounds may be nearly sharp for arbitrarily large hypergraphs and lattices. As an application, we prove that the number of maximal infeasible vectors x=₁××_n for a system of polymatroid inequalities does not exceed max{Q,^logt/c(2Q,)}, where is the number of minimal feasible vectors for the system, , , and c(,) is the unique positive root of the equation 2^c(^c/log–1)=1. This bound is nearly sharp for the Boolean case ={0,1}ⁿ, and it allows for the efficient generation of all minimal feasible sets to a given system of polymatroid inequalities with quasi-polynomially bounded right-hand sides . This research was supported by the National Science Foundation (Grant IIS-0118635), and by the Office of Naval Research (Grant N00014-92-J-1375). The second and third authors are also grateful for the partial support by DIMACS, the National Science Foundation's Center for Discrete Mathematics and Theoretical Computer Science.Mathematics Subject Classification (2000):20E28, 20G40, 20C20     

The number of independent sets in unicyclic graphs with a given diameter

Let U_n,d denote the set of unicyclic graphs with a given diameter d. In this paper, the unique unicyclic graph in U_n,d with the maximum number of independent sets, is characterized.     

Minimizing the number of independent sets in triangle-free regular graphs

Recently, Davies, Jenssen, Perkins, and Roberts gave a very nice proof of the result (due, in various parts, to Kahn, Galvin–Tetali, and Zhao) that the independence polynomial of a $d$-regular graph is maximized by disjoint copies of $K_{d,d}$. Their proof uses linear programming bounds on the distribution of a cleverly chosen random variable. In this paper, we use this method to give lower bounds on the independence polynomial of regular graphs. We also give a new bound on the number of independent sets in triangle-free cubic graphs.     

Graphs with the second largest number of maximal independent sets

Let G be a simple undirected graph. Denote by (respectively, xi(G)) the number of maximal (respectively, maximum) independent sets in G. Erd?s and Moser raised the problem of determining the maximum value of among all graphs of order n and the extremal graphs achieving this maximum value. This problem was solved by Moon and Moser. Then it was studied for many special classes of graphs, including trees, forests, bipartite graphs, connected graphs, (connected) triangle-free graphs, (connected) graphs with at most one cycle, and recently, (connected) graphs with at most r cycles. In this paper we determine the second largest value of and xi(G) among all graphs of order n. Moreover, the extremal graphs achieving these values are also determined.     

Trees with the second largest number of maximal independent sets

A maximal independent set is an independent set that is not a proper subset of any other independent set. In this paper, we determine the second largest number of maximal independent sets among all trees and forests of order n≥4. We also characterize those extremal graphs achieving these values.     

Estimates of the number of independent sets in graphs with a fixed independence number

Attainable estimates of the number of independent sets in graphs with a given size of the maximal independent set are obtained. Three graph classes—trees, forests, and the class of all graphs—are considered. Extremal graphs are described.     

The number of connected sparsely edged graphs

An (n, q) graph has n labeled points, q edges, and no loops or multiple edges. The number of connected (n, q) graphs is f(n, q). Cayley proved that f(n, n^-1) = n^n?2 and Renyi found a formula for f(n, n). Here I develop two methods to calculate the exponential generating function of f(n, n + k) for particular k and so to find a formula for f(n, n + k) for general n. The first method is a recurrent one with respect to k and is well adapted for machine computation, but does not itself provide a proof that it can be continued indefinitely. The second (reduction) method is much less efficient and is indeed impracticable for k greater than 2 or 3, but it supplies the missing proof that the generating function is of a particular form and so that the first method can be continued for all k, subject only to the capacity of the machine.     

The number of strongly connected directed graphs

Solutions of known problems in the enumeration of graphs are obtained. The number of graphs is expressed, by using a lemma proved by Burnside, in terms of the values of an auxiliary combinatorial function of the partitions of a number. These values, expressing the number of strongly connected graphs having a fixed automorphism of a given cyclic type, are determined by a system of linear recurrence relations.Translated from Matematicheskie Zametki, Vol. 8, No. 6, pp. 721–732, December, 1970.