On the number of cliques and cycles in graphs

Abstract

We give a new recursive method to compute the number of cliques and cycles of a graph‎. ‎This method is related‎, ‎respectively to the number of disjoint cliques in the complement graph and to the sum of permanent function over all principal minors of the adjacency matrix of the graph‎. ‎In particular‎, ‎let $G$ be a graph and let $overline {G}$ be its complement‎, ‎then given the chromatic polynomial of $overline {G}$‎, ‎we give a recursive method to compute the number of cliques of $G$‎. ‎Also given the adjacency matrix $A$ of $G$ we give a recursive method to compute the number of cycles by computing the sum of permanent function of the principal minors of $A$‎. ‎In both cases we confront to a new computable parameter which is defined as the number of disjoint cliques in $G$‎.