✦ LIBER ✦

Independence number, connectivity, and r-factors

✍ Scribed by Tsuyoshi Nishimura

Publisher: John Wiley and Sons
Year: 1989
Tongue: English
Weight: 270 KB
Volume: 13
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190130109

No coin nor oath required. For personal study only.

✦ Synopsis

We show that if r L 1 is an odd integer and G is a graph with IV(G)l even such that K ( G ) 2 ( r + 1)2/2 and (r + l)'a(G) 5 4 r ~( G ) , then G has an rfactor; if r 2 2 is even and G is a graph with K ( G ) L r(r + 2)/2 and

then G has an r-factor (where K(G) and a ( G ) denote the connectivity and the independence number of G, respectively).

📜 SIMILAR VOLUMES

Circumferences of k-connected graphs inv

Circumferences of k-connected graphs involving independence numbers

✍ Guantao Chen; Zhiquan Hu; Yaping Wu 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 211 KB 👁 1 views

Let G be a k-connected graph of order n, := (G) the independence number of G, and c(G) the circumference of G. Chvátal and Erdo ˝s proved that if ≤ k then G is hamiltonian. For ≥ k ≥ 2, Fouquet and Jolivet in 1978 made the conjecture that c(G) ≥ k(n+ -k) / . Fournier proved that the conjecture is tr

Independence number and clique minors

✍ Ken-ichi Kawarabayashi; Zi-Xia Song 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 122 KB

## Abstract The Hadwiger number ${h}({G})$ of a graph __G__ is the maximum integer __t__ such that ${K}\_{t}$ is a minor of __G__. Since $\chi({G})\cdot\alpha({G})\geq |{G}|$, Hadwiger's conjecture implies that ${h}({G})\cdot \alpha({G})\geq |{G}|$, where $\alpha({G})$ and $|{G}|$ denote the indepe

The number of maximal independent sets i

The number of maximal independent sets in connected graphs

✍ Zoltán Füredi 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 286 KB 👁 2 views

Generalizing a theorem of Moon and Moser. we determine the maximum number of maximal independent sets in a connected graph on n vertices for n sufficiently large, e.g., n > 50. = I .32. . .). Example 1.2. Let b, = i(C,), where C,z denotes the circuit of length n. Then b, = 3, 6, = 2, b, = 5, and b,

The connected hub number and the connect

The connected hub number and the connected domination number

✍ Peter Johnson; Peter Slater; Matt Walsh 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 189 KB

The average distance and the independenc

The average distance and the independence number

✍ F. R. K. Chung 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 258 KB

We prove that in every connected graph the independence number is at least as large as the average distance between vertices. Theorem. For every connected graph G , we have a ( G ) 2 D ( G ) , with equality if and only if G is a complete graph.

Rainbow connection number and connected

Rainbow connection number and connected dominating sets

✍ L. Sunil Chandran; Anita Das; Deepak Rajendraprasad; Nithin M. Varma 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 167 KB

## Abstract The __rainbow connection number__ of a connected graph is the minimum number of colors needed to color its edges, so that every pair of its vertices is connected by at least one path in which no two edges are colored the same. In this article we show that for every connected graph on __