✦ LIBER ✦

Triangles and Neighbourhoods of Independent Sets in Graphs

✍ Scribed by Andrew M. Robertshaw; Douglas R. Woodall

Publisher: Elsevier Science
Year: 2000
Tongue: English
Weight: 124 KB
Volume: 80
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.2000.1974

No coin nor oath required. For personal study only.

✦ Synopsis

It is proved that a graph of order n contains a triangle if |N(X )| > 1 3 (n+|X |) for every independent set X of vertices. This bound is sharp.

📜 SIMILAR VOLUMES

Projectivity and independent sets in pow

Projectivity and independent sets in powers of graphs

✍ Benoit Larose; Claude Tardif 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 95 KB 👁 1 views

## Abstract We investigate the relationship between projectivity and the structure of maximal independent sets in powers of circular graphs, Kneser graphs and truncated simplices. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 162–171, 2002

Maximal independent sets in bipartite gr

Maximal independent sets in bipartite graphs

✍ Jiuqiang Liu 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 458 KB 👁 1 views

## Abstract A maximal independent set of a graph __G__ is an independent set that is not contained properly in any other independent set of __G.__ In this paper, we determine the maximum number of maximal independent sets among all bipartite graphs of order __n__ and the extremal graphs as well as

Independent sets in random sparse graphs

✍ Pedro G. Gazmuri 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 418 KB

On feedback vertex sets and nonseparatin

On feedback vertex sets and nonseparating independent sets in cubic graphs

✍ Ewald Speckenmeyer 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 341 KB

Let G be an undirected connected graph with n nodes. A subset F of nodes of G is a feedback vertex set (fvs) if G -F is a forest and a subset J of nodes of G is a nonseparating independent set (nsis) if no two nodes of J are adjacent and G -J is connected. f(G), z ( G ) denote the cardinalities of a

Independent perfect domination sets in C

Independent perfect domination sets in Cayley graphs

✍ Jaeun Lee 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 92 KB 👁 1 views

## Abstract In this paper, we show that a Cayley graph for an abelian group has an independent perfect domination set if and only if it is a covering graph of a complete graph. As an application, we show that the hypercube __Q~n~__ has an independent perfect domination set if and only if __Q~n~__ i

Independent sets in tensor graph powers

✍ Alon, Noga (author);Lubetzky, Eyal (author) 📂 Article 📅 2006 🏛 Wiley-Liss Inc. 🌐 English ⚖ 154 KB

## Abstract The tensor product of two graphs, __G__ and __H__, has a vertex set __V__(__G__) × __V__(__H__) and an edge between (__u__,__v__) and (__u__′,__v__′) iff both __u__ __u__′ ∈ __E__(__G__) and __v__ __v__′ ∈ __E__(__H__). Let __A__(__G__) denote the limit of the independence ratios of ten