No Access

On the Extremal Values of the Weighted Integrity of a Graph

Wayne Goddard

School of Mathematical and Statistical Sciences, Clemson University, 105 Sikes Hall, Clemson, SC 29634, USA

E-mail Address: goddard@clemson.edu

Corresponding author.

Search for more papers by this author

and

Julia VanLandingham

School of Mathematical and Statistical Sciences, Clemson University, 105 Sikes Hall, Clemson, SC 29634, USA

Search for more papers by this author

https://doi.org/10.1142/S0219265923500196Cited by:0 (Source: Crossref)

Abstract

The integrity of a graph $G$ is defined as the minimum value of $| S | + m (G - S)$ taken over all $S \subseteq V (G)$ , where $m (H)$ denotes the maximum cardinality of a component of graph $H$ . In this paper, we investigate bounds on the maximum and minimum values of the weighted version of this parameter. We also consider the same question for the related parameter vertex-neighbor-integrity.

Keywords:

References

1. K. S. Bagga, L. W. Beineke, W. Goddard, M. J. Lipman and R. E. Pippert, A survey of integrity, Discrete Applied Math. 37/38 (1990) 13–28. Crossref, Google Scholar
2. C. A. Barefoot, R. Entringer and H. C. Swart, Vulnerability in graphs — A comparative survey, J. Combin. Math. Combin. Computing. 1 (1987) 13–22. Google Scholar
3. M. B. Cozzens and S.-S. Y. Wu, Vertex-neighbor-integrity of trees, Ars Combin. 43 (1996) 169–180. Web of Science, Google Scholar
4. P. G. Drange, M. Dregi and P. van ’t Hof, On the computational complexity of vertex integrity and component order connectivity, Algorithmica 76 (2016) 1181–1202. Crossref, Web of Science, Google Scholar
5. M. J. Gambrell, Vertex-neighbor-integrity of magnifiers, expanders, and hypercubes, Discrete Math. 216 (2000) 257–266. Crossref, Web of Science, Google Scholar
6. W. D. Goddard and H. C. Swart, On the integrity of combinations of graphs, J. Combin. Math. Combin. Comput. 4 (1988) 3–18. Google Scholar
7. W. D. Goddard and H. C. Swart, On some extremal problems in connectivity, In Graph Theory, Combinatorics, and Applications, Vol. 1 (Kalamazoo, MI, 1988), pages 535–551. Wiley, New York, 1991. Google Scholar
8. G. Y. Katona, I. Kovács and K. Varga, The complexity of recognizing minimally tough graphs, Discrete Appl. Math. 294 (2021) 55–84. Crossref, Web of Science, Google Scholar
9. F. Li, X. Zhang and H. Broersma, A polynomial algorithm for weighted scattering number in interval graphs, Discrete Appl. Math. 264 (2019) 118–124. Crossref, Web of Science, Google Scholar
10. S. Ray and J. S. Deogun, Computational complexity of weighted integrity, J. Combin. Math. Combin. Computing. 16 (1994) 65–73. Google Scholar
11. S. Ray, R. Kannan, D. Zhang and H. Jiang, The weighted integrity problem is polynomial for interval graphs, Ars Combin. 79 (2006) 77–95. Web of Science, Google Scholar
12. M. Shi and Z. Wei, A polynomial algorithm for weighted toughness of interval graphs, J. Math. pages Art. ID 6657594, 5, 2021. Google Scholar