Neighbor Isolated Tenacity of Graphs
Aslan, Ersin1
1 Turgutlu Vocational Training School, Celal Bayar University, Turkey.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 49 (2015) no. 4, pp. 269-284.

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 G is defined to beNIT(G) = min {|X|+ c(G/X) / i(G/X), i(G/X) ≥ 1} where the minimum is taken over all X, the cut strategy of G , i(G/X)is the number of components which are isolated vertices of G/X and c(G/X) is the maximum order of the components of G/X. 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.

Reçu le :
Accepté le :
DOI : 10.1051/ita/2016001
Classification : 05C40, 68M10, 68R10
Mots-clés : Graph theory, connectivity, rupture degree, isolated scattering number, tenacity
Aslan, Ersin 1

1 Turgutlu Vocational Training School, Celal Bayar University, Turkey. 
@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 = {https://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  - https://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 https://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. https://numdam.org/articles/10.1051/ita/2016001/

E. Aslan, Edge-neighbor-rupture degree of graphs. J. Appl. Math. 2013 (2013) 783610. | DOI | MR | Zbl

K.S. Bagga, L.W. Beineke, W. Goddard, R.E. Pippert and M.J. Lipman, A survey of integrity, Discrete Appl. Math. 76 (1992) 13–28. | DOI | MR | Zbl

A. Brandstädt, LE V.B. and J.P. Spinrad, Graph classess: a survey. SIAM Monogr. Discrete Math. Appl. Springer (1999). | MR | Zbl

M.B. Cozzens and S.S.Y. Wu, Vertex-neighbor-integrity of trees. Ars Combin. 43 (1996) 169–180. | MR | Zbl

M.B. Cozzens and S.S.Y. Wu, Vertex-neighbor-integrity of powers of cycles. Ars Combin. 48 (1998) 257–270. | MR | Zbl

M.B. Cozzens, D. Moazzami and S. Stueckle, The tenacity of the Harary Graphs. J. Combin. Math. Combin. Comput. 16 (1994) 33–56. | MR | Zbl

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

G. Gunther, 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

H.A. Jung, On a class of posets and the corresponding comparability graphs. J. Combin. Theory, Series B 24 (1978) 125–133. | DOI | MR | Zbl

A. Kirlangic, 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).

F. Li and Q. Ye, The size of a minimum critically m-neighbor-scattered graph. Lect. Notes Comput. Sci. 4616 (2007) 91–101. | DOI | MR | Zbl

Y. Li, S. Zhang, X. Li and Y. Wu, Relationships between tenacity and some other vulnerability parameters. Fangzhi Gaoxiao Jichukexue Xuebao 17 (2004) 1–4. | MR | Zbl

Y. Li, Z. Wei and X. Yue, Tenacity of total graphs. Int. J. Found. Comput. Sci. 25 (2014) 553–562. | DOI | MR | Zbl

D. Moazzami, On the edge-tenacity of graphs, Int. Math. Forum 3 (2008) 929–936. | MR | Zbl

D. Moazzami, Tenacity of a graph with maximum connectivity. Discrete Appl. Math. 159 (2011) 367–380. | DOI | MR | Zbl

B. Piazza, F. Roberts and S. Stueckle, Edge-tenacious networks. Networks 25 (1995) 7–17. | DOI | MR | Zbl

S.Y. Wang, Yx. Yang, S.W. Lin, J. Li and Z.M. Hu, The isolated scattering number of graphs. Acta Math. Sinica, Chinese Series 54 (2011) 861–874. | MR | Zbl

S.Y. Wang, J.S. Wangmu, K. Feng, S.W. Lin and M.Y. Zhang, Relation of the isolated scatting number of a graph and its complement graph. J. Shanxi University (Natural Science Edition) 35 (2012) 206–210.

Z. Wei and S. Zhang, Vertex-neighbour-integrity of composition graphs of paths and cycles. Int. J. Comput. Math. 85 (2008) 727–733. | DOI | MR | Zbl

Z.T. Wei, A. Mai and M. Zhai, Vertex-neighbor-scattering number of graphs. Ars Combin. 102 (2011) 417–426. | MR | Zbl

S.S.Y. Wu and M.B. Cozzens, The minimum size of critically m-neighbour-connected graphs. Ars Combin. 29 (1990) 149–160. | MR | Zbl

Cité par Sources :