An improved lower bound on the independence number of a graph

Michael A. Henning; Christian Löwenstein

doi:10.1016/j.dam.2014.07.001

An improved lower bound on the independence number of a graph

Michael A. Henning, Christian Löwenstein

Mathematics and Applied Mathematics

Ulm University

Research output: Contribution to journal › Article › peer-review

3 Citations (Scopus)

Abstract

The independence number of a graph G, denoted α(G), is the maximum cardinality of an independent set of vertices in G. Our main result is the strengthening of a lower bound for the independence number of a graph due to Löwenstein et al. (2011) who proved that if G is a connected graph of order n and size m, then α(G)≥23n-14m-13. We show that if G does not belong to a specific family of graphs, then α(G)>23n-14m. Further, we characterize the graphs G for which α(G)≤23n-14m.

Original language	English
Pages (from-to)	120-128
Number of pages	9
Journal	Discrete Applied Mathematics
Volume	179
DOIs	https://doi.org/10.1016/j.dam.2014.07.001
Publication status	Published - 31 Dec 2014

Keywords

Independence
Vertex-cover

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

10.1016/j.dam.2014.07.001

Cite this

@article{3524d3fe51a64355aae6ed0b07a29e02,

title = "An improved lower bound on the independence number of a graph",

abstract = "The independence number of a graph G, denoted α(G), is the maximum cardinality of an independent set of vertices in G. Our main result is the strengthening of a lower bound for the independence number of a graph due to L{\"o}wenstein et al. (2011) who proved that if G is a connected graph of order n and size m, then α(G)≥23n-14m-13. We show that if G does not belong to a specific family of graphs, then α(G)>23n-14m. Further, we characterize the graphs G for which α(G)≤23n-14m.",

keywords = "Independence, Vertex-cover",

author = "Henning, {Michael A.} and Christian L{\"o}wenstein",

year = "2014",

month = dec,

day = "31",

doi = "10.1016/j.dam.2014.07.001",

language = "English",

volume = "179",

pages = "120--128",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - An improved lower bound on the independence number of a graph

AU - Henning, Michael A.

AU - Löwenstein, Christian

PY - 2014/12/31

Y1 - 2014/12/31

N2 - The independence number of a graph G, denoted α(G), is the maximum cardinality of an independent set of vertices in G. Our main result is the strengthening of a lower bound for the independence number of a graph due to Löwenstein et al. (2011) who proved that if G is a connected graph of order n and size m, then α(G)≥23n-14m-13. We show that if G does not belong to a specific family of graphs, then α(G)>23n-14m. Further, we characterize the graphs G for which α(G)≤23n-14m.

AB - The independence number of a graph G, denoted α(G), is the maximum cardinality of an independent set of vertices in G. Our main result is the strengthening of a lower bound for the independence number of a graph due to Löwenstein et al. (2011) who proved that if G is a connected graph of order n and size m, then α(G)≥23n-14m-13. We show that if G does not belong to a specific family of graphs, then α(G)>23n-14m. Further, we characterize the graphs G for which α(G)≤23n-14m.

KW - Independence

KW - Vertex-cover

UR - http://www.scopus.com/inward/record.url?scp=84922256844&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2014.07.001

DO - 10.1016/j.dam.2014.07.001

M3 - Article

AN - SCOPUS:84922256844

SN - 0166-218X

VL - 179

SP - 120

EP - 128

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -

An improved lower bound on the independence number of a graph

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this