𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Independence Numbers of Planar Contact Graphs

✍ Scribed by Swanepoel

Publisher
Springer
Year
2002
Tongue
English
Weight
232 KB
Volume
28
Category
Article
ISSN
0179-5376

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Domination numbers of planar graphs
Domination numbers of planar graphs
✍ MacGillivray, G.; Seyffarth, K. πŸ“‚ Article πŸ“… 1996 πŸ› John Wiley and Sons 🌐 English βš– 967 KB

The problem of determining the domination number of a graph is a well known NPhard problem, even when restricted to planar graphs. By adding a further restriction on the diameter of the graph, we prove that planar graphs with diameter two and three have bounded domination numbers. This implies that

Cyclomatic numbers of planar graphs
Cyclomatic numbers of planar graphs
✍ Klara J. Cohn πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 283 KB

For a given planar graph G with a set A of independent vertices, we provide a best-possible upper bound for the minimum cyclomatic number of connected induced subgraphs of G containing A. The extremal graphs are also characterized. @

Circumferences of k-connected graphs inv
Circumferences of k-connected graphs involving independence numbers
✍ Guantao Chen; Zhiquan Hu; Yaping Wu πŸ“‚ Article πŸ“… 2010 πŸ› John Wiley and Sons 🌐 English βš– 211 KB πŸ‘ 1 views

Let G be a k-connected graph of order n, := (G) the independence number of G, and c(G) the circumference of G. ChvΓ‘tal and Erdo ˝s proved that if ≀ k then G is hamiltonian. For β‰₯ k β‰₯ 2, Fouquet and Jolivet in 1978 made the conjecture that c(G) β‰₯ k(n+ -k) / . Fournier proved that the conjecture is tr