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$.
R. E. L. Aldred and C. Thomassen (1997). Counting cycles in cubic graphs. J. Comb. Theory B. 71, 79-84 R. E. L. Aldred and C. Thomassen (2008). On the maximum number of cycles in a planar graph. J. Graph Theory. 57, 255-264 N. Alon and S. Frieldland (2008). The maximum number of perfect matchings in graphs with a given degree sequence. Electron. J. Combin., #N13. 15 N. Biggs (1993). Algebraic Graph Theory. Cambridge Mathematical Library, Cambridge University Press, Cambridge. F. M. Dong, K. M. Koh and K. L. Teo (2005). Choromatic Polynomials and Choromaticity of Garphs. World Scientific Publication. R. C. Entringer and P. J. Slater (1981). On the maximum number of cycles in a graphs. Ars Combin.. 11, 289-294 M. Farber, M. Hujter and Z. Tuza (1993). An upper bound on the number of cliques in a graph. Networks. 23 (3), 207-210 J. H. V. Lint and R .M. Wilson (1992). A Course in Combinatorics. Cambridge University Press, Cambridge. D. B. West (2001). Introduction to Graph Theory. Prentice Hall, 2nd Ed.. D. R. Wood (2007). On the maximum number of cliques in a graph. Graphs Combin.. 23, 337-352
Ariannejad, M. and Emami, M. (2013). On the number of cliques and cycles in graphs. Transactions on Combinatorics, 2(2), 27-33. doi: 10.22108/toc.2013.2872
MLA
Ariannejad, M. , and Emami, M. . "On the number of cliques and cycles in graphs", Transactions on Combinatorics, 2, 2, 2013, 27-33. doi: 10.22108/toc.2013.2872
HARVARD
Ariannejad, M., Emami, M. (2013). 'On the number of cliques and cycles in graphs', Transactions on Combinatorics, 2(2), pp. 27-33. doi: 10.22108/toc.2013.2872
CHICAGO
M. Ariannejad and M. Emami, "On the number of cliques and cycles in graphs," Transactions on Combinatorics, 2 2 (2013): 27-33, doi: 10.22108/toc.2013.2872
VANCOUVER
Ariannejad, M., Emami, M. On the number of cliques and cycles in graphs. Transactions on Combinatorics, 2013; 2(2): 27-33. doi: 10.22108/toc.2013.2872
)
