𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Semiharmonic graphs with fixed cyclomatic number

✍ Scribed by A Dress; S Grünewald; D Stevanović

Publisher
Elsevier Science
Year
2004
Tongue
English
Weight
394 KB
Volume
17
Category
Article
ISSN
0893-9659

No coin nor oath required. For personal study only.

✦ Synopsis

Let the trunk of a graph G be the graph obtained by removing all leaves of G. We prove that, for every integer c _> 2, there are at most finitely many trunks of serniharrnonic graphs with cyclomatic number e--in contrast to the fact established by the last two of the present authors in their paper Serniharmonic Bicyclic Graphs (this journal) that there are infinitely many connected semiharmonie graphs with given cyclomatic number. Further, we prove that there are at most finitely many semiharmonie but not almost semiregular graphs with cyclomatic number c.

📜 SIMILAR VOLUMES

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

On graphs with a fixed number of negativ
On graphs with a fixed number of negative eigenvalues
✍ Aleksander Torgašev 📂 Article 📅 1985 🏛 Elsevier Science 🌐 English ⚖ 374 KB

Let P(n) be the class of all connected graphs having exactly n ~> 1 negative eigenvalues (including their multiplicities). In this paper we prove that the class P(n) contains only finitely many so-called canonical graphs. The analogous statement for the class Q(n) of all connected graphs having exac

The maximum number of edges in a graph w
The maximum number of edges in a graph with fixed edge-degree
✍ R.J. Faudree; J. Sheehan 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 633 KB

Suppose that n i> 2t + 2 (t/> 17). Let G be a graph with n vertices such that its complement is connected and, for all distinct non-adjacent vertices u and v, there are at least t common neighbours. Then we prove that and Furthermore, the results are sharp.