✦ LIBER ✦

A probabilistic upper bound for the edge identification complexity of graphs

✍ Scribed by Eberhard Triesch

Publisher: Elsevier Science
Year: 1994
Tongue: English
Weight: 344 KB
Volume: 125
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(94)90178-3

No coin nor oath required. For personal study only.

✦ Synopsis

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)=(21ogn/log(l/l-p))+O(loglogn). We prove that for each q <+, almost all graphs satisfy c(G)<n-qd(n).

📜 SIMILAR VOLUMES

A new upper bound for the independence n

A new upper bound for the independence number of edge chromatic critical graphs

✍ Rong Luo; Yue Zhao 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 107 KB 👁 2 views

In 1968, Vizing conjectured that if G is a -critical graph with n vertices, then (G) ≤ n / 2, where (G) is the independence number of G. In this paper, we apply Vizing and Vizing-like adjacency lemmas to this problem and prove that (G)<(((5 -6)n) / (8 -6))<5n / 8 if ≥ 6. ᭧ 2010 Wiley

Upper bounds on the edge clique cover nu

Upper bounds on the edge clique cover number of a graph

✍ Robert C. Brigham; Ronald D. Dutton 📂 Article 📅 1984 🏛 Elsevier Science 🌐 English ⚖ 521 KB

An upper bound for the complexity of tra

An upper bound for the complexity of transformation semigroups

✍ Stuart W Margolis; Bret Tilson 📂 Article 📅 1981 🏛 Elsevier Science 🌐 English ⚖ 759 KB

New upper bounds for the chromatic numbe

New upper bounds for the chromatic number of a graph

✍ Ladislav Stacho 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 55 KB 👁 3 views

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

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