𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On local and global independence numbers of a graph

✍ Scribed by Ralph J. Faudree; Zdeněk Ryjáček; Richard H. Schelp

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
121 KB
Volume
132
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

✦ Synopsis

The local independence number i (G) of a graph G at a distance i is the maximum number of independent vertices at distance i from any vertex. We study the impact of restricting i (G) on the (global) independence number (G). Among others, we show that in graphs with bounded diameter, (G) is bounded if and only if i (G) is bounded for at least one i, 2 6 i 6 (diam(G) -1)=4.

📜 SIMILAR VOLUMES

Generalizations of independence and chro
Generalizations of independence and chromatic numbers of a graph
✍ E. Sampathkumar 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 426 KB

Sampathkumar, E., Generalizations of independence and chromatic numbers of a graph, Discrete Mathematics 115 (1993) 2455251. Let G = (V, E) be a graph and k > 2 be an integer. A set S c V is k-independent if every component in the subgraph (S) induced by S has order at most k-1. The general chromati

Independence numbers of locally sparse g
Independence numbers of locally sparse graphs and a Ramsey type problem
✍ Noga Alon 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 409 KB 👁 1 views

Let G = (V, E ) be a graph on n vertices with average degree t 2 1 in which for every vertex u E V the induced subgraph on the set of all neighbors of u is r-colorable. We show that the independence number of G is at least log t , for some absolute positive constant c. This strengthens a well-known

A local independence number condition fo
A local independence number condition for n-extendable graphs
✍ Dingjun Lou 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 273 KB

Let G be a graph and v C V(G). Let Nk(v)= {ulu C V(G) and d(u, v)= k}. It is proved that if G is a connected graph with oo>9(G)~>4 and with even order and if, for each vertex is regular and rd(v)/4]-extendable. All results in this paper are sharp. (~) 1999 Elsevier Science B.V. All rights reserved

On domination and independent domination
On domination and independent domination numbers of a graph
✍ Robert B. Allan; Renu Laskar 📂 Article 📅 1978 🏛 Elsevier Science 🌐 English ⚖ 399 KB

For a graph G, the definitions of doknation number, denoted y(G), and independent domination number, denoted i(G), are given, and the following results are obtained: oorollrrg 1. For any graph G, y(L(G)) = i@(G)), where Z,(G) is the line graph of G. (This $xh!s t.lic rtsult ~(L(T))~i(L(T)), h w ere