×

Graphs whose vertex independence number is unaffected by single edge addition or deletion. (English) Zbl 0792.05116

Authors’ abstract: A graph is \(\beta^ +\)-stable \((\beta^ -\)-stable) if its vertex independence number remains the same upon the addition (deletion) of any edge. We give a constructive characterization of \(\beta^ +\)-stable and \(\beta^ -\)-stable trees.

MSC:

05C75 Structural characterization of families of graphs
05C05 Trees
05C35 Extremal problems in graph theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bauer, D.; Harary, F.; Nieminen, J.; Suffel, C. L., Domination alteration sets in graphs, Discrete Math., 47, 153-161 (1983) · Zbl 0524.05040
[2] Brigham, R. C.; Chinn, Ph. Z.; Dutton, R. D., Vertex domination-critical graphs, Networks, 18, 173-179 (1988) · Zbl 0658.05042
[3] Brigham, R. C.; Dutton, R. D., An extremal problem for edge domination insensitive graphs, Discrete Appl. Math., 20, 113-125 (1988) · Zbl 0638.05031
[4] Brigham, R. C.; Dutton, R. D., Changing and unchanging invariants: the edge clique cover number, Manuscript (1989) · Zbl 0696.05030
[5] B.L. Hartnell and D.F. Rall, The structure of trees lacking edges essential to domination, Ars Combin., to appear.; B.L. Hartnell and D.F. Rall, The structure of trees lacking edges essential to domination, Ars Combin., to appear.
[6] Haynes, T. W.; Lawson, L. M.; Brigham, R. C.; Dutton, R. D., Changing and unchanging of the graphical invariants: minimum and maximum degree, maximum clique size, node independence number and edge independence number, Congr. Numer., 72, 239-252 (1990) · Zbl 0696.05029
[7] Hopkins, G.; Staton, W., Graphs with unique maximum independent sets, Discrete Math., 57, 245-251 (1985) · Zbl 0583.05034
[8] Mitchell, S.; Hedetniemi, S.; Goodman, S., Some linear algorithms on trees, (Proceedings of Sixth Southeastern Conference on Combinatorics, Graph Theory and Computing (1975)), 467-483 · Zbl 0353.05032
[9] Sumner, D. P.; Blitch, P., Domination critical graphs, J. Combin. Theory Ser. B, 34, 65-76 (1983) · Zbl 0512.05055
[10] Zito, J., The maximum number of maximum independent sets for trees, Manuscript (1989)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.