On the number of cliques and cycles in graphs

Document Type: Research Paper

Authors

1 University of zanjan

2 Department of Mathematics, University of Zanjan

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$‎.

Keywords

Main Subjects

References

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
Transactions on Combinatorics

Volume 2, Issue 2
June 2013
Pages 27-33

Files

Share

How to cite

Statistics