ГлавнаяАрхивКратности сумм в явных формулах для подсчёта циклов фиксированной длины в неориентированных графах

Кратности сумм в явных формулах для подсчёта циклов фиксированной длины в неориентированных графах | Прикладная дискретная математика. 2011. № 4(14).

Явные формулы для подсчёта циклов длиной k представляют собой комбинации сумм, соответствующих формам замкнутых маршрутов длиной k. Ранее было показано, что наибольшая кратность суммы в формуле равна [k/2], начиная с k = 8. В данной работе исследуется вопрос, каких значений могут достигать кратности сумм для частных семейств графов: двудольных, без треугольников, планарных, с ограниченными степенями вершин, а также их пересечений. Оказалось, что при больших значениях k только для двудольных графов и для графов со степенями вершин не более трёх наибольшая кратность суммы уменьшается на 1, если k = 2, 3 (mod 4). В случае k ^ 20 возникает ряд исключений, когда для некоторых семейств графов наибольшая кратность уменьшается на 1 или 2.
  • Title Кратности сумм в явных формулах для подсчёта циклов фиксированной длины в неориентированных графах
  • Headline Кратности сумм в явных формулах для подсчёта циклов фиксированной длины в неориентированных графах
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 4(14)
  • Date:
  • DOI
Ключевые слова
prism graphs, shapes of closed walks, counting cycles in graphs, призматические графы, формы замкнутых маршрутов, подсчёт циклов в графах
Авторы
Ссылки
Papadimitriou C. H. and Yannakakis M. The clique problem for planar graphs // Inform. Processing Lett. 1981. V. 13. No. 4, 5. P. 131-133.
flowproblem.ru/cycles/explicit-formulae/ck-graphs - Ck-graphs: FlowProblem. 2011.
cs.anu.edu.au/~bdm/nauty - The nauty page. 2011.
Харари Ф. Теория графов. М.: Мир, 1973. 301 с.
Воропаев А. Н. Учёт обхвата при подсчёте коротких циклов в двудольных графах // Информационные процессы. 2011. Т. 11. №2. С. 225-252.
Alon N., Yuster R., and Zwick U. Finding and counting given length cycles // Algorithmica. 1997. V. 17. No. 3. P. 209-223.
Perepechko S. N. and Voropaev A. N. The number of fixed length cycles in an undirected graph. Explicit formulae in case of small lengths // Int. Conf. "Mathematical Modeling and Computational Physics" (MMCP'2009). Dubna: JINR, 2009. P. 148-149.
Harary F. and Manvel B. On the number of cycles in a graph // Matematicky casopis. 1971. V. 21. No. 1. P. 55-63.
Chang Y. C. and Fu H. L. The number of 6-cycles in a graph // The Bulletin of the Institute of Combinatorics and Its Applications. 2003. V. 39. P. 27-30.
Воропаев А.Н. Вывод явных формул для подсчёта циклов фиксированной длины в неориентированных графах // Информационные процессы. 2011. Т. 11. №1. С. 90-113.
Flum J. and Grohe M. The parameterized complexity of counting problems // SIAM J. Comput. 2004. V.33. No. 4. P. 892-922.
Liskiewicz M., Ogihara M., and Toda S. The complexity of counting self-avoiding walks in subgraphs of two-dimensional grids and hypercubes // Theor. Comput. Sci. 2003. V. 304. No. 1-3. P. 129-156.
Valiant L. G. The complexity of enumeration and reliability problems // SIAM J. Comput. 1979. V.8. No. 3. P. 410-421.
Halford T. R. and Chugg K. M. An algorithm for counting short cycles in bipartite graphs // IEEE Trans. Inform. Theory. 2006. V. 52. No. 1. P. 287-292.
Cardillo A., Scellato S., Latora V., and Porta S. Structural properties of planar graphs of urban street patterns // Phys. Rev. E. 2006. V. 73. No. 6. P. 066107(8).
Newman M. E. J. The structure and function of complex networks // SIAM Rev. 2003. V. 45. No. 2. P. 167-256.
Harary F. and Kommel H. J. Matrix measures for transitivity and balance // J. Math. Sociol. 1979. V.6. No. 2. P. 199-210.
Кратности сумм в явных формулах для подсчёта циклов фиксированной длины в неориентированных графах | Прикладная дискретная математика. 2011. № 4(14).
Кратности сумм в явных формулах для подсчёта циклов фиксированной длины в неориентированных графах | Прикладная дискретная математика. 2011. № 4(14).
Полнотекстовая версия