The brief overview of deterministic graph integrity measures is presented. The well-known relationships between them are given. Some estimates for these measures expressed through the traditional numerical graph parameters are given too. A relationship between the computational complexity of the integrity measures and damage models in graphs is analyzed. Some unsolved problems are pointed.
Download file
Counter downloads: 68
- Title Measures for graph integrity: a comparative survey
- Headline Measures for graph integrity: a comparative survey
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 4(26)
- Date:
- DOI
Keywords
toughness, integrity, vulnerability, graphs, доминирующая целостность, степень разрушения, окрестная целостность, стойкость, прочность, число рассеяния, целостность, графы, scattering number, tenacity, rupture degree, domination integrity, network reliability, neighbour integrityAuthors
References
Zhang Q. L. and Zhang S. G. Edge vulnerability parameters of split graphs // Appl. Math. Lett. 2006. V. 19. P. 916-920.
Zhang S. G., Li X. L., and Han X. L. Computing the scattering number of graphs // Int. J. Comput. Math. 2002. V.79(2). P. 179-187.
Vince A. The integrity of a cubic graph // Discrete Appl. Math. 2004. V. 140(1-3). P. 223-239.
Woeginger G. J. The toughness of split graphs // Discrete Math. 1998. V. 190(1-3). P. 295-297.
Ye Q. On vulnerability of power and total graphs // WSEAS Trans. Math. 2012. No. 11. P. 1028-1038.
Vaidya S. K. and Shah N. H. Domination integrity of total graphs // TWMS J. App. Eng. Math. 2011. No. 4(1). P. 117-126.
Vaidya S. K. and Kothari N. J. Some new results on domination integrity of graphs // Open J. Discrete Math. 2012. No. 2(3). P. 96-98. http://dx.doi.org/10.4236/ojdm.2012.23018
Sundareswaran R. and Swaminathan V. Domination integrity of powers of cycles // Int. J. Math. Res. 2011. No. 3(3). P. 257-265.
Sundareswaran R. and Swaminathan V. Domination integrity in trees // Bulletin Int. Math. Virtual Institute. 2012. No. 2. P. 153-161.
Piazza B. L., Robertst F. S., and Stueckle S. K. Edge-tenacious networks // Networks. 1995. V. 25. P. 7-17.
Ray S., Kannan R., Zhang D., and Jiang H. The weighted integrity problem is polynomial for interval graphs // Ars Combinator. 2006. V. 79. P. 77-95.
Sundareswaran R. and Swaminathan V. Domination integrity in graphs // Proc. Int. Conf. Math. Exp. Physics. Prague, Narosa Publishing House, 2009. P. 46-57.
Ray S. and Deogun J. S. Computational complexity of weighted integrity // J. Combin. Math. Combin. Comput. 1994. V. 16. P. 65-73.
Moazzami D. An algorithm for the computation of edge integrity, I'(T) // Int. J. Contemp. Math. Sci. 2011. No. 6(11). P. 507-516.
Moazzami D. Vulnerability in graphs - a comparative survey // J. Combin. Math. Combin. Comput. 1999. V.30. P. 23-31.
Li Y., Zhang S., and Zhang Q. Vulnerability parameters of split graphs // Int. J. Comput. Math. 2008. V.85(1). P. 19-23.
Mann D. E. The tenacity of trees. Ph. D. Thesis. Northeastern University, 1993.
Laporte G. and Pascoal M. The pipeline and valve location problem // Eur. J. Industr. Eng. 2012. No. 6(3). P. 301-321.
Li F. W. and LiX.L. Computing the rupture degrees of graphs // Proc. 7th Int. Symp. Parallel Architectures, Algorithms and Networks, IEEE Computer Society. Los Alamitos, California, 2004. P. 368-373.
Katona G. Y. Toughness and edge-toughness // Discrete Math. 1997. V. 164. P. 187-196.
Kratsch D., Kloks T., and Muller H. Measuring the vulnerability for classes of intersection graphs // Discrete Appl. Math. 1997. V.77(3). P. 259-270.
Hayes J. P. A graph model for fault-tolerant computing system // IEEE Trans. Comput. 1976. V. 25(9). P. 875-884.
DeLaViaE., Pepper R., and Waller B. Lower bounds for the domination number // Discussiones Math. Graph Theory. 2010. V.30(3). P. 475-487.
Downey R. G. and Fellows M. R. Parameterized complexity. N.Y.: Springer Verlag, 1999.
Drange P. G., Dregi M. S., and Hof P. On the computational complexity of vertex integrity. 2014. http://arxiv.org/abs/1403.6331v1.
Fellows M. and Stueckle S. The immersion order, forbidden subgraphs and the complexity of network integrity //J. Combin. Math. Combin. Comput. 1989. No. 6. P. 23-32.
Goddard W. and Swart H. C. Integrity in graphs: bounds and basic //J. Combin. Math. Combin. Comput. 1990. No. 7. P. 139-151.
CozzensM.B. and WuS.Y. Vertex-neighbor-integrity of trees // Ars Combinator. 1996. V. 43. P. 169-180.
Cozzens M. B. and Wu S. Y. Bounds of edge-neighbor-integrity of graphs // Australasian J. Combinatorics. 1997. V. 15. P. 71-80.
Bykova V. V. Analysis parameterized algorithms on the bases of elasticity to functions complexity // J. Siberian Federal University. Math. & Physics. 2011. No. 4(2). P. 195-207.
Chvatal V. Tough graphs and Hamiltonian circuits // Discrete Math. 1973. No. 5. P. 215-228.
Clark L. H., Entringer R. C., and Fellows M. R. Computational complexity of integrity //J. Combin. Math. Combin. Comput. 1987. No. 2. P. 179-191.
Bauer D., Hakimi S. L., and Schmeichel E. Recognizing tough graphs is NP-hard // Discrete Appl. Math. 1990. V.28. P. 191-195.
Bodlaender H. L., Hendriks A., Grigoriev A., and Grigorieva N. V. The valve location problem in simple network topologies // Informs. J. Computing. 2010. V. 22(3). P. 433-442.
Bykova V. V. Parameterized complexity and elasticity of the algorithms // Proc. 14th Appl. Stochastic Models and Data Analysis Int. Conf. (ASMDA2011). Rome, Italy, 2011. P. 219-225.
Barefoot C. A., Entringer R., and Swart H. C. Integrity of trees and powers of cycles // Congr. Numer. 1987. V. 58. P. 103-114.
Bagga K. S., Beineke L. W., Goddard W.D., et al. A survey of integrity // Discrete Appl. Math. 1992. No. 37/38. P. 13-28.
Bagga K.S., Beineke L.W., Lipman M. J., and Pippert R. E. Edge-integrity: a survey // Discrete Math. 1994. V. 124. P. 3-12.
Barefoot C. A., EntringerR., and Swart H. C. Vulnerability in graphs - a comparative survey // J. Combin. Math. Combin. Comput. 1987. No. 1. P. 13-22.
Avizienis A. The design of fault tolerant computers // AFIPS Conf. Proc. NY, USA, 1967. P. 733-743.
Хорошевский В. Г. Архитектура вычислительных систем. М.: МГТУ им. Н. Э. Баумана, 2008.
Atici M., Crawford R., and Ernst C. New upper bounds for the integrity of cubic graphs // Int. J. Computer Math. 2004. No. 81(11). P. 1341-1348.
Atici M., Crawford R., and Ernst C. The integrity of small cage graphs // Australasian J. Combinatorics. 2009. No. 43. P. 39-55.
Салий В. Н Оптимальные реконструкции графов // Современные проблемы дифференц. геометрии и общей алгебры. Саратов: Изд-во Сарат. ун-та, 2008. С. 59-65.
Салий В. Н Минимальные примитивные расширения ориентированных графов // Прикладная дискретная математика. 2008. №1(1). С. 116-119.
Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: Вильямс, 2012.
Кристофидес Н. Теория графов: алгоритмический подход. М.: Мир, 1978.
Ловас Л., Пламмер М. Прикладные задачи теории графов. Теория паросочетаний в математике, физике, химии. М.: Мир, 1998.
Каравай М. Ф. Инвариантно-групповой подход к исследованию k-отказоустойчивых структур // Автоматика и телемеханика. 2000. №1. С. 144-156.
Каравай М. Ф. Применение теории симметрии к анализу и синтезу отказоустойчивых систем // Автоматика и телемеханика. 1996. №6. С. 159-173.
Дундар П., Айтак А., Айтак В. Вычисление индекса доступности и окрестной целостности графа // Матем. заметки. 2005. №78(5). С. 676-686.
Емеличев В. А, Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. М.: Книжный дом «ЛИБРОКОМ», 2012.
Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.
Дундар П., Айтак А. Выражения целостности тотальных графов через некоторые характеристики графов // Матем. заметки. 2004. №76(5). С. 714-722.
Грязнов Н. Г., Димитриев Ю. К., Мелентьев В. А. Оптимизация отказоустойчивого вложения диагностического графа в тороидальные структуры живучих вычислительных систем // Автоматика и телемеханика. 2003. №4. С. 133-152.
Абросимов М. Б. Графовые модели отказоустойчивости. Саратов: Изд-во Сарат. ун-та, 2012.
Быкова В. В. FPT-алгоритмы и их классификация на основе эластичности // Прикладная дискретная математика. 2011. №2(12). С. 40-48.
Громов Ю. Ю., Драчёв В. О., Набатов К. А., Иванова О. Г. Синтез и анализ живучести сетевых систем. М.: Машиностроение, 2007.
Абросимов М. Б. О сложности некоторых задач, связанных с расширениями графов // Матем. заметки. 2004. №88(5). С. 643-650.
Measures for graph integrity: a comparative survey | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2014. № 4(26).
Download full-text version
Counter downloads: 201