Previous |  Up |  Next


vulnerability; integrity; neighbor-integrity
Let $G$ be a graph. A vertex subversion strategy of $G$, say $S$, is a set of vertices in $G$ whose closed neighborhood is removed from $G$. The survival-subgraph is denoted by $G/S$. The Neighbor-Integrity of $G$, $\mathop {\mathrm NI}(G)$, is defined to be $\mathop {\mathrm NI}(G) = \min _{S\subseteq V(G)} \lbrace |S|+c(G/S)\rbrace $, where $S$ is any vertex subversion strategy of $G$, and $c(G/S)$ is the maximum order of the components of $G/S$. In this paper we give some results connecting the neighbor-integrity and binary graph operations.
[1] Atıcı, M.; Kırlangı, A.: Counterexamples to the theorems of integrity of prisms and ladders. J. Comb. Math. Comb. Comput. 34 (2000), 119–127. MR 1772790
[2] Bagga, K. S.; Beineke, L. W.; Goddard, W. D.; Lipman, M. J.; Pippert, R. E.: A survey of integrity. Discrete Appl. Math. 37/38 (1992), 13–28. DOI 10.1016/0166-218X(92)90122-Q | MR 1176842
[3] Bagga, K. S.; Beineke, L. W.; Lipman, M. J.; Pippert, R. E.: Edge-integrity: a survey. Discrete Math. 124 (1994), 3–12. DOI 10.1016/0012-365X(94)90084-1 | MR 1258837
[4] Barefoot, C. A.; Entringer, R.; Swart, H.: Vulnerability in graphs—a comparative survey. J. Comb. Math. Comb. Comput. 1 (1987), 13–22. MR 0888829
[5] Cozzens, M. B.: Stability measures and data fusion networks. Graph Theory of New York 26 (1994), 8–14.
[6] Cozzens, M. B.; Moazzami, D.; Stueckle, S.: The tenacity of a graph. Graph theory, combinatorics, algorithms and applications, Alavi, Y. et al. (eds.), Wiley, New York, 1995, pp. 1111–1122. MR 1405887
[7] Cozzens, M. B.; Wu, S. Y.: Edge-neighbor-integrity of trees. Australas J. Comb. 10 (1994), 163–174. MR 1296949
[8] Cozzens, M. B.; Wu, S. Y.: Vertex-neighbor-integrity of trees. Ars. Comb. 43 (1996), 169–180. MR 1415985
[9] Cozzens, M. B.; Wu, S. Y.: Bounds of edge-neighbor-integrity of graphs. Australas J. Comb. 15 (1997), 71–80. MR 1448231
[10] Goddard, W.; Swart, H. C.: On the toughness of a graph. Quaest. Math. 13 (1990), 217–232. DOI 10.1080/16073606.1990.9631613 | MR 1068711
[11] Gambrell, Marci J.: Vertex-neighbor-integrity of magnifiers, expanders and hypercubes. Discrete Math. 216 (2000), 257–266. DOI 10.1016/S0012-365X(99)00352-0 | MR 1750866 | Zbl 0957.05067
[12] Harary, F.: Graph Theory. Addison-Wesley Publishing Company, 1969. MR 0256911 | Zbl 0196.27202
[13] Kırlangı, A.: The edge-integrity of some graphs. J. Comb. Math. Comb. Comput. 37 (2001), 139–148. MR 1834438
[14] Kırlangı, A.; Ozan, A.: The neighbour-integrity of total graphs. Int. J. Comput. Math. 76 (2000), 25–33. DOI 10.1080/00207160008805006 | MR 1808796
Partner of
EuDML logo