𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A local independence number condition for n-extendable graphs

✍ Scribed by Dingjun Lou

Publisher
Elsevier Science
Year
1999
Tongue
English
Weight
273 KB
Volume
195
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

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 Keywords." Local condition; Independence number; n-extendable graph All graphs considered are finite, undirected and simple.

Let n be a positive integer and G be a graph with v>~2n + 2. G is said to be n-extendable if G has n independent edges and any n independent edges of G are contained in a perfect matching of G.

Let G be a graph and vE V(G). Let Nk

and H be a subgraph of G. Then we use the notation Ns(v)=N(v)NS and NH(v)=N(v)N V(H). And ds(v)= INs(v)[ and dH(V)= [NH(v)[. Let x be a real number. We denote by r x] the least integer m such that m>>,x and by Ix] the largest integer m such that m ~x.

For the terminology and notation not defined in this paper, the reader is referred to [3].

πŸ“œ SIMILAR VOLUMES

Independence number in n-extendable grap
Independence number in n-extendable graphs
✍ Peter Maschlanka; Lutz Volkmann πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 756 KB

Let G be a connected graph with p vertices and n a positive integer with 1 dn <(p/2) -1. G is said to be O-extendable if G has a perfect matching. G is said to be n-extendable if G has a matching of size n and every matching of size n in G extends to (i.e. is a subset of) a perfect matching. It is s

Generalized degree conditions for graphs
Generalized degree conditions for graphs with bounded independence number
✍ Ralph Faudree; Ronald J. Gould; Linda Lesniak; Terri Lindquester πŸ“‚ Article πŸ“… 1995 πŸ› John Wiley and Sons 🌐 English βš– 511 KB

We consider a generalized degree condition based on the cardinality of the neighborhood union of arbitrary sets of r vertices. We show that a Dirac-type bound on this degree in conjunction with a bound on the independence number of a graph is sufficient to imply certain hamiltonian properties in gra

On local and global independence numbers
On local and global independence numbers of a graph
✍ Ralph J. Faudree; ZdenΔ›k RyjÑček; Richard H. Schelp πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 121 KB

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 i

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

The independence number condition for th
The independence number condition for the existence of a spanning f-tree
✍ Hikoe Enomoto; Kenta Ozeki πŸ“‚ Article πŸ“… 2010 πŸ› John Wiley and Sons 🌐 English βš– 123 KB πŸ‘ 1 views

## Abstract Let __G__ be a graph and __f__ be a mapping from __V__(__G__) to the positive integers. A subgraph __T__ of __G__ is called an __f__‐tree if __T__ forms a tree and __d__~__T__~(__x__)≀__f__(__x__) for any __x__∈__V__(__T__). We propose a conjecture on the existence of a spanning __f__‐t