✦ LIBER ✦

The average distance and the independence number

✍ Scribed by F. R. K. Chung

Publisher: John Wiley and Sons
Year: 1988
Tongue: English
Weight: 258 KB
Volume: 12
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190120213

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

The average Steiner distance of a graph

✍ Dankelmann, Peter; Oellermann, Ortrud R.; Swart, Henda C. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 384 KB 👁 2 views

The average distance p(G) of a graph G is the average among the distances between all pairs of vertices in G. For n 2 2, the average Steiner n-distance ,4G) of a connected graph G is the average Steiner distance over all sets of n vertices in G. It is shown that for a connected weighted graph G, pu,

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 Average Distribution of Inversive

On the Average Distribution of Inversive Pseudorandom Numbers

✍ Harald Niederreiter; Igor E. Shparlinski 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 146 KB

The inversive congruential method is an attractive alternative to the classical linear congruential method for pseudorandom number generation. The authors have recently introduced a new method for obtaining nontrivial upper bounds on the multidimensional discrepancy of inversive congruential pseudor

A lower bound on the independence number

A lower bound on the independence number of arbitrary hypergraphs

✍ Thiele, Torsten 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 104 KB 👁 3 views

We present a lower bound on the independence number of arbitrary hypergraphs in terms of the degree vectors. The degree vector of a vertex v is given by d is the number of edges of size m containing v. We define a function f with the property that any hypergraph H = (V, E) satisfies α(H) ≥ v∈V f (d

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

Auditor independence and the new indepen

Auditor independence and the new independence standards board

✍ Robert W. Rouse; Gary Previts 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 411 KB

## He currently chairs the Financial Ethics Committee of the International Association of Financial Executives Institutes. I n search of additional fees, big accounting firms now offer "extended" audit services to corporate clients, including both external and internal audit functions. But there h