پیوندهای مفید
اخبار و اعلانات
آمار
| تعداد نشریات | 44 |
| تعداد شمارهها | 1,877 |
| تعداد مقالات | 15,278 |
| تعداد مشاهده مقاله | 43,731,211 |
| تعداد دریافت فایل اصل مقاله | 17,563,322 |
On the number of cliques and cycles in graphs | ||
| Transactions on Combinatorics | ||
| مقاله 4، دوره 2، شماره 2، شهریور 2013، صفحه 27-33 اصل مقاله (304.29 K) | ||
| نوع مقاله: Research Paper | ||
| شناسه دیجیتال (DOI): 10.22108/toc.2013.2872 | ||
| نویسندگان | ||
| Masoud Ariannejad* 1؛ Mojgan Emami2 | ||
| 1University of zanjan | ||
| 2Department of Mathematics, University of Zanjan | ||
| چکیده | ||
| 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$. | ||
| کلیدواژهها | ||
| graph؛ cycle؛ Clique | ||
| مراجع | ||
|
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
| ||
|
آمار تعداد مشاهده مقاله: 5,417 تعداد دریافت فایل اصل مقاله: 3,049 |
||