𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A tight upper bound for group testing in graphs

✍ Scribed by Peter Damaschke

Publisher
Elsevier Science
Year
1994
Tongue
English
Weight
481 KB
Volume
48
Category
Article
ISSN
0166-218X

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

A new upper bound for total colourings o
A new upper bound for total colourings of graphs
✍ AbdΓ³n SΓ‘nchez-Arroyo πŸ“‚ Article πŸ“… 1995 πŸ› Elsevier Science 🌐 English βš– 118 KB

We give a new upper bound on the total chromatic number of a graph. This bound improves the results known for some classes of graphs. The bound is stated as follows: ZT ~< Z~ + L l3 ~ J + 2, where Z is the chromatic number, Z~ is the edge chromatic number (chromatic index) and ZT is the total chroma

An upper bound for the path number of a
An upper bound for the path number of a graph
✍ Alan Donald πŸ“‚ Article πŸ“… 1980 πŸ› John Wiley and Sons 🌐 English βš– 529 KB

## Abstract The path number of a graph __G__, denoted __p(G)__, is the minimum number of edge‐disjoint paths covering the edges of __G.__ LovΓ‘sz has proved that if __G__ has __u__ odd vertices and __g__ even vertices, then __p(G)__ ≀ 1/2 __u__ + __g__ ‐ 1 ≀ __n__ ‐ 1, where __n__ is the total numbe

An upper bound for the minimum rank of a
An upper bound for the minimum rank of a graph
✍ Avi Berman; Shmuel Friedland; Leslie Hogben; Uriel G. Rothblum; Bryan Shader πŸ“‚ Article πŸ“… 2008 πŸ› Elsevier Science 🌐 English βš– 137 KB
A probabilistic upper bound for the edge
A probabilistic upper bound for the edge identification complexity of graphs
✍ Eberhard Triesch πŸ“‚ Article πŸ“… 1994 πŸ› Elsevier Science 🌐 English βš– 344 KB

Given a finite graph G=( V, E), what is the minimum number c(G) of incidence tests which are needed in the worst case to identify an unknown edge e\*EE? The number c(G) was first studied by Aigner and Triesch (1988), where it was shown that for almost all graphs in the random graph model where d(n)