𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Independence number in n-extendable graphs

✍ Scribed by Peter Maschlanka; Lutz Volkmann

Publisher
Elsevier Science
Year
1996
Tongue
English
Weight
756 KB
Volume
154
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

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 shown that in every nonbipartite, n-extendable graph G the independence number a(G) satisfies a(G) <(p/2) -n and that this upper bound is sharp for all n and p. If G is a nonbipartite, n-extendable graph with 4n+2> p, then G is Hamiltonian, and if 4n> p+2k, then G is (n + 2 + k)-connected for all integers k 2 0. Furthermore, the saturation number s(G) of a graph G is defined to be the smallest cardinal@ of a maximal matching of G. Some relations between the parameters s(G) and a(G) in n-extendable graphs G of order p are presented.

πŸ“œ SIMILAR VOLUMES

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

Hamiltonian cycles in n-extendable graph
Hamiltonian cycles in n-extendable graphs
✍ Ken-ichi Kawarabayashi; Katsuhiro Ota; Akira Saito πŸ“‚ Article πŸ“… 2002 πŸ› John Wiley and Sons 🌐 English βš– 88 KB

## Abstract A graph __G__ of order at least 2__n__+2 is said to be __n__‐extendable if __G__ has a perfect matching and every set of __n__ independent edges extends to a perfect matching in __G__. We prove that every pair of nonadjacent vertices __x__ and __y__ in a connected __n__‐extendable graph

A note on n-extendable graphs
A note on n-extendable graphs
✍ Qinglin Yu πŸ“‚ Article πŸ“… 1992 πŸ› John Wiley and Sons 🌐 English βš– 249 KB

## Abstract A graph __G__ having a perfect matching is called n‐__extendable__ if every matching of size __n__ of __G__ can be extended to a perfect matching. In this note, we show that if __G__ is an __n__‐extendable nonbipartite graph, then __G__ + __e__ is (__n__ ‐ 1)‐extendable for any edge e Ο΅

On the independence number of random gra
On the independence number of random graphs
✍ A.M. Frieze πŸ“‚ Article πŸ“… 1990 πŸ› Elsevier Science 🌐 English βš– 239 KB

Let (Y(G~,~) denote the independence number of the random graph Gn,p. Let d = np. We show that if E > 0 is fixed then with probability going to 1 as n + m cu(G& -$t (log d -log log dlog 2 + 1) < 7 provided d, s d = o(n), where d, is some fixed constant.