The tenacity of a graph is a measure of the vulnerability of a graph. In this paper we investigate a refinement that involves the neighbor isolated version of this parameter. The neighbor isolated tenacity of a noncomplete connected graph is defined to beNIT(G) = min {|X|+ c(G/X) / i(G/X), i(G/X) ≥ 1} where the minimum is taken over all , the cut strategy of , is the number of components which are isolated vertices of and is the maximum order of the components of . Next, the relations between neighbor isolated tenacity and other parameters are determined and the neighbor isolated tenacity of some special graphs are obtained. Moreover, some results about the neighbor isolated tenacity of graphs obtained by graph operations are given.
Accepté le :
DOI : 10.1051/ita/2016001
Mots-clés : Graph theory, connectivity, rupture degree, isolated scattering number, tenacity
@article{ITA_2015__49_4_269_0, author = {Aslan, Ersin}, title = {Neighbor {Isolated} {Tenacity} of {Graphs}}, journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications}, pages = {269--284}, publisher = {EDP-Sciences}, volume = {49}, number = {4}, year = {2015}, doi = {10.1051/ita/2016001}, mrnumber = {3507247}, zbl = {1346.68142}, language = {en}, url = {http://archive.numdam.org/articles/10.1051/ita/2016001/} }
TY - JOUR AU - Aslan, Ersin TI - Neighbor Isolated Tenacity of Graphs JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2015 SP - 269 EP - 284 VL - 49 IS - 4 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ita/2016001/ DO - 10.1051/ita/2016001 LA - en ID - ITA_2015__49_4_269_0 ER -
%0 Journal Article %A Aslan, Ersin %T Neighbor Isolated Tenacity of Graphs %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2015 %P 269-284 %V 49 %N 4 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ita/2016001/ %R 10.1051/ita/2016001 %G en %F ITA_2015__49_4_269_0
Aslan, Ersin. Neighbor Isolated Tenacity of Graphs. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 49 (2015) no. 4, pp. 269-284. doi : 10.1051/ita/2016001. http://archive.numdam.org/articles/10.1051/ita/2016001/
Edge-neighbor-rupture degree of graphs. J. Appl. Math. 2013 (2013) 783610. | DOI | MR | Zbl
,A survey of integrity, Discrete Appl. Math. 76 (1992) 13–28. | DOI | MR | Zbl
, , , and ,A. Brandstädt, LE V.B. and J.P. Spinrad, Graph classess: a survey. SIAM Monogr. Discrete Math. Appl. Springer (1999). | MR | Zbl
Vertex-neighbor-integrity of trees. Ars Combin. 43 (1996) 169–180. | MR | Zbl
and ,Vertex-neighbor-integrity of powers of cycles. Ars Combin. 48 (1998) 257–270. | MR | Zbl
and ,The tenacity of the Harary Graphs. J. Combin. Math. Combin. Comput. 16 (1994) 33–56. | MR | Zbl
, and ,M.B. Cozzens, D. Moazzami and S. Stueckle, The Tenacity of a Graph: Graph Theory, Combinatorisc, Algorithms and Applications. Vol. 2 of Proc. of the 7th Quadrennial International Conference on the Theory and Applications of Graphs. Wiley, New York (1995) 1111–1122. | MR | Zbl
Neighbor connectivity in regular graphs. Discrete Appl. Math. 11 (1985) 233–243. | DOI | MR | Zbl
,F. Harary, Graph Theory. Addison-Wesley, New York (1994). | MR | Zbl
On a class of posets and the corresponding comparability graphs. J. Combin. Theory, Series B 24 (1978) 125–133. | DOI | MR | Zbl
,Graph operations and neighbor-integrity. Math. Bohem. 3 (2004) 245–254. | DOI | MR | Zbl
,F. Li and X. Li, Computational Complexity and Bounds for Neighbor-Scattering Number of Graphs. Proc. of the 8th International Symposium on Parallel Architectures. Algorithms and Networks (2005).
The size of a minimum critically m-neighbor-scattered graph. Lect. Notes Comput. Sci. 4616 (2007) 91–101. | DOI | MR | Zbl
and ,Relationships between tenacity and some other vulnerability parameters. Fangzhi Gaoxiao Jichukexue Xuebao 17 (2004) 1–4. | MR | Zbl
, , and ,Tenacity of total graphs. Int. J. Found. Comput. Sci. 25 (2014) 553–562. | DOI | MR | Zbl
, and ,On the edge-tenacity of graphs, Int. Math. Forum 3 (2008) 929–936. | MR | Zbl
,Tenacity of a graph with maximum connectivity. Discrete Appl. Math. 159 (2011) 367–380. | DOI | MR | Zbl
,Edge-tenacious networks. Networks 25 (1995) 7–17. | DOI | MR | Zbl
, and ,The isolated scattering number of graphs. Acta Math. Sinica, Chinese Series 54 (2011) 861–874. | MR | Zbl
, , , and ,Relation of the isolated scatting number of a graph and its complement graph. J. Shanxi University (Natural Science Edition) 35 (2012) 206–210.
, , , and ,Vertex-neighbour-integrity of composition graphs of paths and cycles. Int. J. Comput. Math. 85 (2008) 727–733. | DOI | MR | Zbl
and ,Vertex-neighbor-scattering number of graphs. Ars Combin. 102 (2011) 417–426. | MR | Zbl
, and ,The minimum size of critically m-neighbour-connected graphs. Ars Combin. 29 (1990) 149–160. | MR | Zbl
and ,Cité par Sources :