✦ LIBER ✦

Cyclomatic numbers of connected induced subgraphs

✍ Scribed by Xingxing Yu

Publisher: Elsevier Science
Year: 1992
Tongue: English
Weight: 509 KB
Volume: 105
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(92)90150-e

No coin nor oath required. For personal study only.

✦ Synopsis

We give an upper bound for w(A), the minimum cyclomatic number of connected induced subgraphs containing a given independent set A of vertices in a given graph G. We also give an upper bound for w(A) when G is triangle-free.

We show that these two bounds are best possible. Similar results are obtained for A to be a matching of G.

📜 SIMILAR VOLUMES

Factors and Connected Induced Subgraphs

✍ Keiko Kotani 📂 Article 📅 2001 🏛 Springer Japan 🌐 English ⚖ 83 KB

Graphs with most number of three point i

Graphs with most number of three point induced connected subgraphs

✍ F.T. Boesch; X. Li; J. Rodriguez 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 678 KB

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. @

On the cyclomatic number of a hypergraph

✍ B.D. Acharya 📂 Article 📅 1979 🏛 Elsevier Science 🌐 English ⚖ 572 KB

## This note generalizes the notion of cyclomatic number (or cycle rank) from Graph Theory to Hypergraph Theory and links it up with the concept of planarity in hypergraphs which was recently introducea by R.P. Jones. Sharp bounds are obtained for the cyclomatic number of the planar hypergraphs an

Chromatic numbers of subgraphs

✍ F. Galvin 📂 Article 📅 1973 🏛 Springer Netherlands 🌐 English ⚖ 124 KB

On the number of induced subgraphs of tr

On the number of induced subgraphs of trees

✍ J.W. Moon 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 416 KB

used generating functions to obtain explicit formulas for the number of induced subgraphs with components of given sizes contained in trees T~ belonging to three particular families of trees. Using a different approach, we derive a more general result that contains their formulas as special cases.