Vulnerability of nearest neighbor graphs

Agarwal, 1995 N. Alon, P. Seymour, R. Thomas, A separator theorem for graphs with an excluded minor and its applications, in: STOC 90 Proceedings of the Twenty Second Annual ACM Symposium on Theory of Computing, 1990. Alon, 1990, A separator theorem for nonplanar graphs, J. Amer. Math. Soc., 3, 801, 10.1090/S0894-0347-1990-1065053-0 Alon, 1994, Planar separators, SIAM J. Discrete Math., 7, 184, 10.1137/S0895480191198768 Ballister, 2009, Highly connected random geometric graphs, Discrete Appl. Math., 157, 309, 10.1016/j.dam.2008.03.001 Barefoot, 1987, Vulnerability in graphs—a comparative survey, J. Combin. Math. Combin. Comput., 1, 12 Bauer, 2006, Toughness in graphs—a survey, Graphs Combin., 22, 1, 10.1007/s00373-006-0649-0 Benko, 2009, Asymptotic bounds on the integrity of graphs and separator theorems, SIAM J. Discrete Math., 23, 265, 10.1137/070692698 Cozzens, 1995, The tenacity of a graph, 1111 Djidjev, 1985, A separator theorem for graphs of fixed genus, Serdica Math. J., 11, 319 Gilbert, 1984, A separator theorem for graphs of bounded genus, J. Algorithms, 5, 391, 10.1016/0196-6774(84)90019-1 Gilbert, 1982 Goddard, 1990, Integrity in graphs: bounds and basics, J. Combin. Math. Combin. Comput., 7, 139 Jung, 1978, On a class of posets and the corresponding comparability graphs, J. Combin. Theory Ser. B, 24, 125, 10.1016/0095-8956(78)90013-8 K. Kawarabayashi, B. Reed, A separator theorem in minor-closed classes, in: 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, FOCS 2010, Las Vegas, Nevada, October 23–26, 2010, pp. 153–162. Li, 2005, Rupture degree of graphs, Int. J. Comput. Math., 82, 793, 10.1080/00207160412331336062 Lipton, 1979, A separator theorem for planar graphs, SIAM J. Appl. Math., 36, 177, 10.1137/0136016 Merkle, 1996, Logarithmic convexity and inequalities for the gamma function, J. Math. Anal. Appl., 203, 369, 10.1006/jmaa.1996.0385 Miller, 1997, Separators for sphere-packings and nearest neighbor graphs, J. ACM, 44, 1, 10.1145/256292.256294 Miller, 1998, Geometric separators for finite-element meshes, SIAM J. Sci. Comput., 19, 364, 10.1137/S1064827594262613 Moazzami, 2011, Tenacity of a graph with maximum connectivity, Discrete Appl. Math., 159, 367, 10.1016/j.dam.2010.11.008 Mohar, 1989, Isoperimetric numbers of graphs, J. Combin. Theory Ser. B, 47, 274, 10.1016/0095-8956(89)90029-4 S.-H. Teng, Points, spheres, and separators, a unified geometric approach to graph partitioning, Ph.D. Thesis, School of Computer Science, Carnegie Mellon University, 1991.