Euler's work on the Bridges of Koenigsberg problem is usually regarded as the birth of Graph Theory. But combinatorialists were not alone studying graph-like structures. In the beginning of the 20th century, sociologists started studying social networks. The idea of "six degrees of separation" (any human on Earth can reach any other by at most six acquaintance links) is from this period. More recently, physicists took to looking at real networks focusing on degree distributions, hubs, communities, preferential growth and other evolution hypotheses, and the like. In this lecture we will review the main points of modern Network Science, exploring scale-free networks, degree correlations, robustness and its relationship to spreading phenomena, e.g., pandemic modeling.

An independent set of G = (V;E) is a subset S of V such that no two vertices are adjacent. S ⊆ V is a maximal independent set (mis for short) if it is not properly contained in any other independent set of G. The family of mis of G is denoted by M(G) and its cardinality is μ(G). Prodinger and Tichy (1982) introduced the Fibonacci number f(G) of a graph G as the number of independent sets of G, not necessarily maximal, including the empty set. Valiant (1979) showed that the problem of counting the number of mis is #P-complete for a general graph. Füredi (1987) determined a bound for μ(G) when G is a connected graph with at least 50 vertices. Independently, Griggs et al. (1988) established the same bound and characterized the extremal graphs that attain this bound for graphs with six or more vertices. This problem has been studied for various graph classes, including trees (Wilf (1986)), graphs with at most one cycle (Jou and Chang (1997)), graphs with r cycles (Sagan and Vatter (2006) and Goh et al. (2006)), bipartite graphs (Liu (1993)), triangle-free graphs (Hujter and Tuza (1993) and Chang and Jou (1999)) and unicyclic graphs (Koh et al. (2008) and Pedersen and Vestergaard (2005)). Euler (2005) calculated μ(G) when G is a grid graph with up to five rows. The problem of enumerating all maximal independent sets of a graph has also been considered by different authors. For a general connected graphs Tsukiyama et al. (1977) developed the best algorithm. Leung (1984) enumerated all mis of interval graphs, chordal graphs and circular arc graphs. Yu and Chen (1993) solved the problem for permutation graphs. Hota et al. (1999) did the same for trapezoid graphs. The intersection graph I(G) of the family of all maximal independent sets of a graph G is called the Independent Graph of G. Each vertex of I(G) corresponds to a mis of G and two vertices are adjacent in I(G) if their corresponding mis have non-empty intersection in G. Analogously, the Clique Graph K(G) is the intersection graph of all cliques of G. Ortiz and Villanueva (2012) determined μ(G) and generated the family of mis in a caterpillar graph and characterized the independent graph. Ortiz and Villanueva (2017) did the same for grid graphs with two rows. In this work we survey results on these problems related to independent sets: counting independent sets and enumerating maximal independent sets. abstract available in pdf format