✦ LIBER ✦

On the independence ratio of a graph

✍ Scribed by Michael O. Albertson; Joan P. Hutchinson

Publisher: John Wiley and Sons
Year: 1978
Tongue: English
Weight: 318 KB
Volume: 2
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190020102

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

This paper presents some recent results on lower bounds for independence ratios of graphs of positive genus and shows that in a limiting sense these graphs have the same independence ratios as do planar graphs. This last result is obtained by an application of Menger's Theorem to show that every triangulation of a surface of positive genus has a short cycle which does not separate the graph and is non‐contractible on that surface.

📜 SIMILAR VOLUMES

On the Density of Subgraphs in a Graph w

On the Density of Subgraphs in a Graph with Bounded Independence Number

✍ Pavel Valtr 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 260 KB

Let \_(n, m, k) be the largest number \_ # [0, 1] such that any graph on n vertices with independence number at most m has a subgraph on k vertices with at lest \_ } ( k 2 ) edges. Up to a constant multiplicative factor, we determine \_(n, m, k) for all n, m, k. For log n m=k n, our result gives \_(

k-Independence and thek-residue of a gra

k-Independence and thek-residue of a graph

✍ Jelen, Frank 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 282 KB 👁 2 views

Favaron, Mahéo, and Saclé proved that the residue of a simple graph G is a lower bound on its independence number α(G). For k ∈ N, a vertex set X in a graph is called k-independent, if the subgraph induced by X has maximum degree less than k. We prove that a generalization of the residue, the k-resi

Bounds on the Size of the Likelihood Rat

Bounds on the Size of the Likelihood Ratio Test of Independence in a Contingency Table

✍ W.Y. Loh; X.J. Yu 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 323 KB

Bounds are obtained on the limiting size of the nominal level- \(\alpha\) likelihood ratio test of independence in a \(r \times c\) contingency table. The situations considered include sampling with both marginal totals random and with one margin fixed. Upper and lower bounds are obtained. The limit

On the Maximum Number of Independent Cyc

On the Maximum Number of Independent Cycles in a Bipartite Graph

✍ Hong Wang 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 404 KB

Let G=(V 1 , V 2 ; E ) be a bipartite graph with |V 1 |= |V 2 | =n 2k, where k is a positive integer. Suppose that the minimum degree of G is at least k+1. We show that if n>2k, then G contains k vertex-disjoint cycles. We also show that if n=2k, then G contains k&1 quadrilaterals and a path of orde

The independence number of an edge-chrom

The independence number of an edge-chromatic critical graph

✍ Douglas R. Woodall 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 77 KB 👁 1 views

A graph G with maximum degree and edge chromatic number (G)> is edge--critical if (G -e) = for every edge e of G. It is proved here that the vertex independence number of an edge--critical graph of order n is less than 3 5 n. For large , this improves on the best bound previously known, which was ro

On the hamiltonian path graph of a graph

✍ George R. T. Hendry 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 491 KB 👁 1 views

The hamiltonian path graph H(F) of a graph F is that graph having the same vertex set as F and in which two vertices u and u are adjacent if and only if F contains a hamiltonian u -u path. First, in response to a conjecture of Chartrand, Kapoor and Nordhaus, a characterization of nonhamiltonian grap