Isolated rupture degree of trees and gear graphs

Feng Wei Li

Abstract


The isolated rupture degree for a connected graph G is defined as ir(G) = max{i(G-S)-|S|-m(G-S):S is element C(G)}, where i(G-S) and m(G-S), respectively, denote the number of components which are isolated vertices and the order of a largest component in G-S. C(G) denotes the set of all cut-sets of G. The isolated rupture degree is a new graph parameter which can be used to measure the vulnerability of networks. In this paper, we firstly give a recursive algorithm for computing the isolated rupture degree of trees, and determine the maximum and minimum isolated rupture degree of trees with given order and maximum degree. Then, the exact value of isolated rupture degree of gear graphs are given. In the final, we determine the rupture degree of the Cartesian product of two special graphs and a special permutation graph.

Keywords


isolated rupture degree; vulnerability; ir-set; recursive algorithm; cartesian product; gear graph

Full Text:

PDF

References


BAREFOOT C.A., ENTRINGER R., SWART H. Vulnerability in graphs - A comparative survey. J. Combin. Math. Combin. Comput. 1987, 1(38), pp. 12-22.

BONDY J.A., MURTY U.S.R. Graph Theory with Applications. UK: The Macmillan Press Ltd. and USA: Elsevier Science Publishing Co., Inc., 1976.

BRANDSTÄDT A., LE V.B., SPINRAD J.P. Graph Classess: A Survey. USA, Philadelphia: SIAM Monographs on Discrete Mathematics and Applications, 1999.

CHARTRAND G., HARARY F. Planar permutation graphs. Ann. Inst. H. Poincare Sec. B (N.S.). 1967, 3(4), pp. 433-438.

CHVÁTAL V. Tough graphs and Hamiltonian circuits. Discrete Mathematics. 1973, 5(3), pp. 215-228, doi: 10.1016/0012-365X(73)90138-6.

COZZENS M., MOAZZAMI D., STUECKLE S. The tenacity of a graph. In: Proc. of the 7th International Conference on the Theory and Applications of Graphs, USA. New York: Wiley, 1995, pp. 1111-1122.

JUNG H.A. On a class of posets and the corresponding comparability graphs. Journal of Combinatorial Theory Series B. 1978, 24(2), pp. 125-133, doi: 10.1016/0095-8956(78)90013-8.

KIRLANGIC A., BACAK-TURAN G. On the rupture degree of a graph. Neural Network World. 2012, 22(1), pp. 39-51, doi: 10.14311/NNW.2012.22.003.

LI F.W. On isolated rupture degree of graphs. Utilitas Mathematica. 2015, 96, pp. 33-47.

LI F.W., LI X.L. Computing the rupture degrees of graphs. In: Proc. of the 7th international symposium on parallel architectures, algorithms and networks, USA, Los Alamitos, California. IEEE computer society, 2004, pp. 368-373, doi: 10.1109/ISPAN.2004.1300507.

LI F.W., YE Q.F., SHENG B.H. Computing rupture degrees of some graphs. WSEAS transactions on mathematics. 2012, 11(1), pp. 23-33.

LI Y.K., ZHANG S.G., LI X.L. Rupture degree of graphs. Int. J. Comput. Math. 2005, 82(7), pp. 793-803, doi: 10.1080/00207160412331336062.

LI F.W., LI X.L. On the Integrity of Graphs. In: Proc. of the 16th IASTED International Conference on Parallel and Distributed Computing and Systems, USA, MIT, Cambridge. Acta Press, 2004, pp. 577-582.

LI Y.K. The rupture degree of trees. Int. J. Comput. Math. 2008, 85(11), pp. 1629-1635, doi: 10.1080/00207160701553367.

ROMAN S. Advanced linear algebra. New York: Springer-Verlag, 1992, doi: 10.1007/9781475721782.

WANG S.Y., YANG Y.X, LIN W.S, LI J., HU Z.M. The isolated scattering number of graphs. Acta Math. Sinica. 2011, 54(5), pp. 861{874. In Chinese.

ZHANG S.G., LI X.L., HAN X.L. Computing the scattering number of graphs. Int. J. Comput. Math. 2002, 79(2), pp. 179{187, doi: 10.1080/00207160211919.




DOI: http://dx.doi.org/10.14311/NNW.2015.%25x

Refbacks

  • There are currently no refbacks.


Should you encounter an error (non-functional link, missing or misleading information, application crash), please let us know at nnw.ojs@fd.cvut.cz.
Please, do not use the above address for non-OJS-related queries (manuscript status, etc.).
For your convenience we maintain a list of frequently asked questions here. General queries to items not covered by this FAQ shall be directed to the journal editoral office at nnw@fd.cvut.cz.