TY - JOUR
ID - 2872
TI - On the number of cliques and cycles in graphs
JO - Transactions on Combinatorics
JA - TOC
LA - en
SN - 2251-8657
AU - Ariannejad, Masoud
AU - Emami, Mojgan
AD - University of zanjan
AD - Department of Mathematics, University of Zanjan
Y1 - 2013
PY - 2013
VL - 2
IS - 2
SP - 27
EP - 33
KW - graph
KW - cycle
KW - Clique
DO - 10.22108/toc.2013.2872
N2 - 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$.
UR - https://toc.ui.ac.ir/article_2872.html
L1 - https://toc.ui.ac.ir/article_2872_183b76bba4970596525b994ca1ef4997.pdf
ER -