×

A lower bound on independence in terms of degrees. (English) Zbl 1218.05036

Summary: We prove a new lower bound on the independence number of a simple connected graph in terms of its degrees.

MSC:

05C07 Vertex degrees
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C40 Connectivity
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Y. Caro, New results on the independence number, Technical Report, Tel-Aviv University, 1979.; Y. Caro, New results on the independence number, Technical Report, Tel-Aviv University, 1979.
[2] Harant, J.; Rautenbach, D., Independence in connected graphs, Discrete Applied Mathematics, 159, 79-86 (2011) · Zbl 1208.05098
[3] Harant, J.; Schiermeyer, I., On the independence number of a graph in terms of order and size, Discrete Math., 232, 131-138 (2001) · Zbl 1030.05091
[4] Harant, J.; Schiermeyer, I., A lower bound on the independence number of a graph in terms of degrees, Discuss. Math. Graph Theory, 26, 431-437 (2006) · Zbl 1138.05051
[5] J. Håstad, Clique is hard to approximate within \(n^{1 - \epsilon}\); J. Håstad, Clique is hard to approximate within \(n^{1 - \epsilon}\)
[6] Lozin, V.; de Werra, D., Foreword: special issue on stability in graphs and related topics, Discrete Appl. Math., 132, 1-2 (2003) · Zbl 1028.01503
[7] V.K. Wei, A lower bound on the stability number of a simple graph, Technical Memorandum, TM 81-11217-9, Bell laboratories, 1981.; V.K. Wei, A lower bound on the stability number of a simple graph, Technical Memorandum, TM 81-11217-9, Bell laboratories, 1981.
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.