Average lower independence in trees and outerplanar graphs

Sheng Bau; Michael A. Henning; Peter Dankelmann

Average lower independence in trees and outerplanar graphs

Sheng Bau, Michael A. Henning, Peter Dankelmann

University of KwaZulu-Natal

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

Abstract

For a vertex v of a graph G = (V,E), the lower independence number i _v(G) of G relative to v is the minimum cardinality of a maximal independent set in G that contains v. The average lower independence number of G is i_av(G) = 1/|V| ∑_v∈V i_v(G). In this paper, we show that if G is a tree of order n, then i_av(G) ≥ 2√n + 0(1), while if G is an outer-planar graph of order n, then i _av(G) ≥ 2√n/3 + 0(1). Both bounds are asymptotically sharp.

Original language	English
Pages (from-to)	147-159
Number of pages	13
Journal	Ars Combinatoria
Volume	69
Publication status	Published - Oct 2003
Externally published	Yes

Keywords

Average lower independence
Outerplanar graphs
Trees

ASJC Scopus subject areas

General Mathematics

Cite this

@article{aa52ec5b76d8456c950fd6723f132070,

title = "Average lower independence in trees and outerplanar graphs",

abstract = "For a vertex v of a graph G = (V,E), the lower independence number i v(G) of G relative to v is the minimum cardinality of a maximal independent set in G that contains v. The average lower independence number of G is iav(G) = 1/|V| ∑v∈V iv(G). In this paper, we show that if G is a tree of order n, then iav(G) ≥ 2√n + 0(1), while if G is an outer-planar graph of order n, then i av(G) ≥ 2√n/3 + 0(1). Both bounds are asymptotically sharp.",

keywords = "Average lower independence, Outerplanar graphs, Trees",

author = "Sheng Bau and Henning, {Michael A.} and Peter Dankelmann",

year = "2003",

month = oct,

language = "English",

volume = "69",

pages = "147--159",

journal = "Ars Combinatoria",

issn = "0381-7032",

publisher = "Charles Babbage Research Centre",

}

TY - JOUR

T1 - Average lower independence in trees and outerplanar graphs

AU - Bau, Sheng

AU - Henning, Michael A.

AU - Dankelmann, Peter

PY - 2003/10

Y1 - 2003/10

N2 - For a vertex v of a graph G = (V,E), the lower independence number i v(G) of G relative to v is the minimum cardinality of a maximal independent set in G that contains v. The average lower independence number of G is iav(G) = 1/|V| ∑v∈V iv(G). In this paper, we show that if G is a tree of order n, then iav(G) ≥ 2√n + 0(1), while if G is an outer-planar graph of order n, then i av(G) ≥ 2√n/3 + 0(1). Both bounds are asymptotically sharp.

AB - For a vertex v of a graph G = (V,E), the lower independence number i v(G) of G relative to v is the minimum cardinality of a maximal independent set in G that contains v. The average lower independence number of G is iav(G) = 1/|V| ∑v∈V iv(G). In this paper, we show that if G is a tree of order n, then iav(G) ≥ 2√n + 0(1), while if G is an outer-planar graph of order n, then i av(G) ≥ 2√n/3 + 0(1). Both bounds are asymptotically sharp.

KW - Average lower independence

KW - Outerplanar graphs

KW - Trees

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

M3 - Article

AN - SCOPUS:0242350470

SN - 0381-7032

VL - 69

SP - 147

EP - 159

JO - Ars Combinatoria

JF - Ars Combinatoria

ER -

Average lower independence in trees and outerplanar graphs

Abstract

Keywords

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this