Some Result on Weak-Tenacity of A Graph

Document Type : Research Paper


faculties members / Damghan University


Connectivity has been used in the past to describe the stability of graphs. If two graphs, have the same connectivity, then it dose not distinguish between these graphs. That is, the connectivity is not a good measure of graph stability. Then we need other graph parameters to describe the stability. Suppose that two graphs have the same connectivity and the order (the number of vertices or edges) of the largest components of these graphs are not equal. Hence, we say that these graphs must be different in respect to stability and so we can define a new measure which distinguishes these graphs. In this paper, the Weak-Tenacity of graph G is introduced as a new measure of stability in this sense and it is defined as

Tw(G) = minSV(G) { (|S| + me (G-S)) / ω(G-S) : ω(G-S) > 1},

Where me(G-S) denotes the number of, edges of the largest component of G-S. At last, We give the Weak-Tenacity of graphs obtained via various operations.


  1. C. A. Barefoot, R. Entringer, H. C. Swart, Integrity of tree and powers of cycles, Congr.

Numer., 58, 103–114 (1987).

  1. J. A. Bondy, U. S. R. Murty, Graph Theory with Applications, Macmillan London and

Elsevier, New York, (1976).

  1. V. Chvatal, Tough graphs and Hamiltonian Circuits. Discrete Math., 5, 111–119 (1973).
  2. M. D. Cozzens, D. Moazzami, S. Stueckle, The Tenacity of a Graph, Graph Theory,

Combinatorics, and Algorithems (Yousef Alavi and Allen Schwenk eds.) wiley, New Yourk, 1111–1121 (1995).

  1. W. D. Godard, H. C. Swart, On the toughness of a graph. Quaestions Math., 13, 217–232 (1990).
  2. A. Kirlangic, On the weak-integrity of graphs, J. Mathematical Modeling and Algorithems, 2, 81–95 (2003).
  3. A. Kirlangic, On the weak-integrity of trees, Turk J. math., 27, 375–388 (2003).
  4. D. Moazami, Stability Measure of a Graph-a Survey, J. Utilitas Mathematica, 57, 171– 191 (2000).
  5. D. R. Woodall, The binding number of a graph and its Anderson number, J. Combin. Theory Ser. B., 15, 225–255 (1973).