✦ LIBER ✦

On Hadwiger's number— a problem of the Nordhaus-Gaddum type

✍ Scribed by M. Stiebitz

Publisher: Elsevier Science
Year: 1992
Tongue: English
Weight: 700 KB
Volume: 101
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(92)90611-i

No coin nor oath required. For personal study only.

✦ Synopsis

Stiebitz, M., On Hadwiger's number-A problem of the Nordhaus-Gaddum type, Discrete Mathematics 101 (1992) 307-317. The Hadwiger number of a graph G = (V, E), denoted by q(G), is the maximum size of a complete graph to which G can be contracted. Let %((n, k):= {G 1 IV(G)1 = n and n(G) = k}. We shall investigate F(n, k) := max{n(G) 1 GE %((n, k)} and f(n, k):= min{q(G) 1 G E %(n, k)}. Problems of this type were first considered by Nordhaus and Gaddum (1956) for the chromatic number. The main results are contained in Theorem 1.4 and Theorem 1.6.

📜 SIMILAR VOLUMES

On a Nordhaus-Gaddum type problem for in

On a Nordhaus-Gaddum type problem for independent domination

✍ E.J. Cockayne; G. Fricke; C.M. Mynhardt 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 254 KB

Let i(G) (i(G), respectively) be the independent domination number (i.e. smallest cardinality of a maximal independent vertex subset) of the p-vertex graph G (the complement G of G, respectively). We prove limp~[max~ i(G)i(Cr)/p 2] = 1/16.

On the number of solutions of a nonlinea

On the number of solutions of a nonlinear Dirichlet problem

✍ A.C Lazer; P.J McKenna 📂 Article 📅 1981 🏛 Elsevier Science 🌐 English ⚖ 540 KB

On a Problem of Erdös in Additive Number

On a Problem of Erdös in Additive Number Theory

✍ Dieter Wolke 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 263 KB

In 1954 Lorentz and Erdo s showed that there are very thin sets of positive integers complementary to the set of primes. In particular, there is an A N with (ii) every n n 0 can be written as n=a+ p, a # A, p prime. Erdo s conjectured that the bound (i) could be sharpened to o(ln 2 x) or even O(ln

On the solution of the caterer problem

✍ J. W. Gaddum; A. J. Hoffman; D. Sokolowsky 📂 Article 📅 1954 🏛 John Wiley and Sons 🌐 English ⚖ 343 KB

On the problem of approximating the numb

On the problem of approximating the number of bases of a matriod

✍ Y. Azar; A.Z. Broder; A.M. Frieze 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 237 KB

A Note on the Neumann Problem for a Quas

A Note on the Neumann Problem for a Quasilinear Elliptic Problem of a Nonmonotone Type

✍ Ivan Hlaváček 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 155 KB

The existence and uniqueness of a weak solution of a Neumann problem is discussed for a second-order quasilinear elliptic equation in a divergence form. The note is a continuation of a recent paper, where mixed boundary value problems were considered, which guaranteed the coerciveness of the problem