Geodesic
Measures for graph integrity: a~comparative survey
Prikladnaâ diskretnaâ matematika, no. 4 (2014), pp. 96-111.

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Keywords: graphs, vulnerability, integrity, toughness, scattering number, tenacity, rupture degree, domination integrity, network reliability, neighbour integrity. 
@article{PDM_2014_4_a10,
     author = {V. V. Bykova},
     title = {Measures for graph integrity: a~comparative survey},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {96--111},
     publisher = {mathdoc},
     number = {4},
     year = {2014},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2014_4_a10/}
}
TY  - JOUR
AU  - V. V. Bykova
TI  - Measures for graph integrity: a~comparative survey
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2014
SP  - 96
EP  - 111
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2014_4_a10/
LA  - ru
ID  - PDM_2014_4_a10
ER  - 
%0 Journal Article
%A V. V. Bykova
%T Measures for graph integrity: a~comparative survey
%J Prikladnaâ diskretnaâ matematika
%D 2014
%P 96-111
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2014_4_a10/
%G ru
%F PDM_2014_4_a10
V. V. Bykova. Measures for graph integrity: a~comparative survey. Prikladnaâ diskretnaâ matematika, no. 4 (2014), pp. 96-111. http://geodesic.mathdoc.fr/item/PDM_2014_4_a10/

[1] Abrosimov M. B., “O slozhnosti nekotorykh zadach, svyazannykh s rasshireniyami grafov”, Matem. zametki, 88:5 (2004), 643–650 | DOI | MR

[2] Abrosimov M. B., Grafovye modeli otkazoustoichivosti, Izd-vo Sarat. un-ta, Saratov, 2012

[3] Bykova V. V., “FPT-algoritmy i ikh klassifikatsiya na osnove elastichnosti”, Prikladnaya diskretnaya matematika, 2011, no. 2(12), 40–48

[4] Gromov Yu. Yu., Drachëv V. O., Nabatov K. A., Ivanova O. G., Sintez i analiz zhivuchesti setevykh sistem, Mashinostroenie, M., 2007

[5] Gryaznov N. G., Dimitriev Yu. K., Melentev V. A., “Optimizatsiya otkazoustoichivogo vlozheniya diagnosticheskogo grafa v toroidalnye struktury zhivuchikh vychislitelnykh sistem”, Avtomatika i telemekhanika, 2003, no. 4, 133–152 | Zbl

[6] Geri M., Dzhonson D., Vychislitelnye mashiny i trudnoreshaemye zadachi, Mir, M., 1982 | MR

[7] Dundar P., Aitak A., “Vyrazheniya tselostnosti totalnykh grafov cherez nekotorye kharakteristiki grafov”, Matem. zametki, 76:5 (2004), 714–722 | DOI | MR | Zbl

[8] Dundar P., Aitak A., Aitak V., “Vychislenie indeksa dostupnosti i okrestnoi tselostnosti grafa”, Matem. zametki, 78:5 (2005), 676–686 | DOI | MR | Zbl

[9] Emelichev V. A., Melnikov O. I., Sarvanov V. I., Tyshkevich R. I., Lektsii po teorii grafov, Knizhnyi dom “LIBROKOM”, M., 2012

[10] Karavai M. F., “Primenenie teorii simmetrii k analizu i sintezu otkazoustoichivykh sistem”, Avtomatika i telemekhanika, 1996, no. 6, 159–173 | MR | Zbl

[11] Karavai M. F., “Invariantno-gruppovoi podkhod k issledovaniyu $k$-otkazoustoichivykh struktur”, Avtomatika i telemekhanika, 2000, no. 1, 144–156 | Zbl

[12] Kormen T., Leizerson Ch., Rivest R., Algoritmy: postroenie i analiz, Vilyams, M., 2012

[13] Kristofides N., Teoriya grafov: algoritmicheskii podkhod, Mir, M., 1978 | MR

[14] Lovas L., Plammer M., Prikladnye zadachi teorii grafov. Teoriya parosochetanii v matematike, fizike, khimii, Mir, M., 1998

[15] Salii V. N., “Minimalnye primitivnye rasshireniya orientirovannykh grafov”, Prikladnaya diskretnaya matematika, 2008, no. 1(1), 116–119

[16] Salii V. N., “Optimalnye rekonstruktsii grafov”, Sovremennye problemy differents. geometrii i obschei algebry, Izd-vo Sarat. un-ta, Saratov, 2008, 59–65

[17] Khoroshevskii V. G., Arkhitektura vychislitelnykh sistem, MGTU im. N. E. Baumana, M., 2008

[18] Atici M., Crawford R., Ernst C., “New upper bounds for the integrity of cubic graphs”, Int. J. Computer Math., 81:11 (2004), 1341–1348 | DOI | MR | Zbl

[19] Atici M., Crawford R., Ernst C., “The integrity of small cage graphs”, Australasian J. Combinatorics, 43 (2009), 39–55 | MR | Zbl

[20] Avizienis A., “The design of fault tolerant computers”, AFIPS Conf. Proc., NY, USA, 1967, 733–743

[21] Bagga K. S., Beineke L. W., Goddard W. D., et al., “A survey of integrity”, Discrete Appl. Math., 37/38 (1992), 13–28 | DOI | MR | Zbl

[22] Bagga K. S., Beineke L. W., Lipman M. J., Pippert R. E., “Edge-integrity: a survey”, Discrete Math., 124 (1994), 3–12 | DOI | MR | Zbl

[23] Barefoot C. A., Entringer R., Swart H. C., “Vulnerability in graphs – a comparative survey”, J. Combin. Math. Combin. Comput., 1 (1987), 13–22 | MR | Zbl

[24] Barefoot C. A., Entringer R., Swart H. C., “Integrity of trees and powers of cycles”, Congr. Numer., 58 (1987), 103–114 | MR | Zbl

[25] Bauer D., Hakimi S. L., Schmeichel E., “Recognizing tough graphs is NP-hard”, Discrete Appl. Math., 28 (1990), 191–195 | DOI | MR | Zbl

[26] Bodlaender H. L., Hendriks A., Grigoriev A., Grigorieva N. V., “The valve location problem in simple network topologies”, Informs. J. Computing, 22:3 (2010), 433–442 | DOI | MR | Zbl

[27] Bykova V. V., “Parameterized complexity and elasticity of the algorithms”, Proc. 14th Appl. Stochastic Models and Data Analysis Int. Conf. (ASMDA 2011), Rome, Italy, 2011, 219–225

[28] Bykova V. V., “Analysis parameterized algorithms on the bases of elasticity to functions complexity”, J. Siberian Federal University. Math. Physics, 4:2 (2011), 195–207

[29] Chvatal V., “Tough graphs and Hamiltonian circuits”, Discrete Math., 5 (1973), 215–228 | DOI | MR | Zbl

[30] Clark L. H., Entringer R. C., Fellows M. R., “Computational complexity of integrity”, J. Combin. Math. Combin. Comput., 2 (1987), 179–191 | MR | Zbl

[31] Cozzens M. B., Wu S. Y., “Vertex-neighbor-integrity of trees”, Ars Combinator., 43 (1996), 169–180 | MR | Zbl

[32] Cozzens M. B., Wu S. Y., “Bounds of edge-neighbor-integrity of graphs”, Australasian J. Combinatorics, 15 (1997), 71–80 | MR | Zbl

[33] DeLaVia E., Pepper R., Waller B., “Lower bounds for the domination number”, Discussiones Math. Graph Theory, 30:3 (2010), 475–487 | DOI | MR

[34] Downey R. G., Fellows M. R., Parameterized complexity, Springer Verlag, N.Y., 1999 | MR | Zbl

[35] Drange P. G., Dregi M. S., Hof P., On the computational complexity of vertex integrity, 2014, arXiv: 1403.6331v1

[36] Fellows M., Stueckle S., “The immersion order, forbidden subgraphs and the complexity of network integrity”, J. Combin. Math. Combin. Comput., 6 (1989), 23–32 | MR | Zbl

[37] Goddard W., Swart H. C., “Integrity in graphs: bounds and basic”, J. Combin. Math. Combin. Comput., 7 (1990), 139–151 | MR | Zbl

[38] Hayes J. P., “A graph model for fault-tolerant computing system”, IEEE Trans. Comput., 25:9 (1976), 875–884 | DOI | MR | Zbl

[39] Katona G. Y., “Toughness and edge-toughness”, Discrete Math., 164 (1997), 187–196 | DOI | MR | Zbl

[40] Kratsch D., Kloks T., Muller H., “Measuring the vulnerability for classes of intersection graphs”, Discrete Appl. Math., 77:3 (1997), 259–270 | DOI | MR | Zbl

[41] Laporte G., Pascoal M., “The pipeline and valve location problem”, Eur. J. Industr. Eng., 6:3 (2012), 301–321 | DOI

[42] Li F. W., Li X. L., “Computing the rupture degrees of graphs”, Proc. 7th Int. Symp. Parallel Architectures, Algorithms and Networks, IEEE Computer Society, Los Alamitos, California, 2004, 368–373

[43] Li Y., Zhang S., Zhang Q., “Vulnerability parameters of split graphs”, Int. J. Comput. Math., 85:1 (2008), 19–23 | DOI | MR | Zbl

[44] Mann D. E., The tenacity of trees, Ph. D. Thesis, Northeastern University, 1993

[45] Moazzami D., “Vulnerability in graphs – a comparative survey”, J. Combin. Math. Combin. Comput., 30 (1999), 23–31 | MR | Zbl

[46] Moazzami D., “An algorithm for the computation of edge integrity, $I'(T)$”, Int. J. Contemp. Math. Sci., 6:11 (2011), 507–516 | MR | Zbl

[47] Ray S., Deogun J. S., “Computational complexity of weighted integrity”, J. Combin. Math. Combin. Comput., 16 (1994), 65–73 | MR | Zbl

[48] Ray S., Kannan R., Zhang D., Jiang H., “The weighted integrity problem is polynomial for interval graphs”, Ars Combinator., 79 (2006), 77–95 | MR | Zbl

[49] Sundareswaran R., Swaminathan V., “Domination integrity in graphs”, Proc. Int. Conf. Math. Exp. Physics, Narosa Publishing House, Prague, 2009, 46–57

[50] Sundareswaran R., Swaminathan V., “Domination integrity of powers of cycles”, Int. J. Math. Res., 3:3 (2011), 257–265

[51] Sundareswaran R., Swaminathan V., “Domination integrity in trees”, Bulletin Int. Math. Virtual Institute, 2 (2012), 153–161 | MR

[52] Piazza B. L., Robertst F. S., Stueckle S. K., “Edge-tenacious networks”, Networks, 25 (1995), 7–17 | DOI | MR | Zbl

[53] Vaidya S. K., Shah N. H., “Domination integrity of total graphs”, TWMS J. App. Eng. Math., 4:1 (2011), 117–126 | MR

[54] Vaidya S. K., Kothari N. J., “Some new results on domination integrity of graphs”, Open J. Discrete Math., 2:3 (2012), 96–98 | DOI

[55] Vince A., “The integrity of a cubic graph”, Discrete Appl. Math., 140:1–3 (2004), 223–239 | DOI | MR | Zbl

[56] Woeginger G. J., “The toughness of split graphs”, Discrete Math., 190:1–3 (1998), 295–297 | DOI | MR | Zbl

[57] Ye Q., “On vulnerability of power and total graphs”, WSEAS Trans. Math., 11 (2012), 1028–1038

[58] Zhang Q. L., Zhang S. G., “Edge vulnerability parameters of split graphs”, Appl. Math. Lett., 19 (2006), 916–920 | DOI | MR | Zbl

[59] Zhang S. G., Li X. L., Han X. L., “Computing the scattering number of graphs”, Int. J. Comput. Math., 79:2 (2002), 179–187 | DOI | MR | Zbl