𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Analysis of the impact of the number of edges in connected graphs on the computational complexity of the independent set problem

✍ Scribed by D. S. Malyshev

Book ID
114994297
Publisher
Pleiades Publishing
Year
2012
Tongue
English
Weight
473 KB
Volume
6
Category
Article
ISSN
1990-4789

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

The number of maximal independent sets i
The number of maximal independent sets in connected graphs
✍ ZoltΓ‘n FΓΌredi πŸ“‚ Article πŸ“… 1987 πŸ› John Wiley and Sons 🌐 English βš– 286 KB πŸ‘ 2 views

Generalizing a theorem of Moon and Moser. we determine the maximum number of maximal independent sets in a connected graph on n vertices for n sufficiently large, e.g., n > 50. = I .32. . .). Example 1.2. Let b, = i(C,), where C,z denotes the circuit of length n. Then b, = 3, 6, = 2, b, = 5, and b,

On the extremal number of edges in hamil
On the extremal number of edges in hamiltonian connected graphs
✍ Tung-Yang Ho; Cheng-Kuan Lin; Jimmy J.M. Tan; D. Frank Hsu; Lih-Hsing Hsu πŸ“‚ Article πŸ“… 2010 πŸ› Elsevier Science 🌐 English βš– 421 KB

a b s t r a c t Assume that n and Ξ΄ are positive integers with 3 ≀ Ξ΄ < n. Let hc(n, Ξ΄) be the minimum number of edges required to guarantee an n-vertex graph G with minimum degree Ξ΄(G) β‰₯ Ξ΄ to be hamiltonian connected.

The number of maximal independent sets i
The number of maximal independent sets in a connected graph
✍ Jerrold R. Griggs; Charles M. Grinstead; David R. Guichard πŸ“‚ Article πŸ“… 1988 πŸ› Elsevier Science 🌐 English βš– 1021 KB

We determine the maximum on n vertices can have, and we a question of Wilf. number of maximal independent sets which a connected graph completely characterize the extremal graphs, thereby answering \* Partially supported by NSF grant number DIMS-8401281. t Partially supported by NSF grant number D S