𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the Hosoya index and the Merrifield–Simmons index of graphs with a given clique number

✍ Scribed by Kexiang Xu

Publisher
Elsevier Science
Year
2010
Tongue
English
Weight
377 KB
Volume
23
Category
Article
ISSN
0893-9659

No coin nor oath required. For personal study only.

✦ Synopsis

The Hosoya index and the Merrifield-Simmons index of a graph are defined as the total number of the matchings (including the empty edge set) and the total number of the independent vertex sets (including the empty vertex set) of the graph, respectively. Let W n,k be the set of connected graphs with n vertices and clique number k. In this note we characterize the graphs from W n,k with extremal (maximal and minimal) Hosoya indices and the ones with extremal (maximal and minimal) Merrifield-Simmons indices, respectively.

📜 SIMILAR VOLUMES

On the Ramsey number of trees versus gra
On the Ramsey number of trees versus graphs with large clique number
✍ Ronald J. Gould; Michael S. Jacobson 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 335 KB

Chvatal established that r(T,, K,,) = (m -1 ) ( n -1 ) + 1, where T, , , is an arbitrary tree of order m and K, is the complete graph of order n. This result was extended by Chartrand, Gould, and Polimeni who showed K, could be replaced by a graph with clique number n and order n + 5 provided n 2 3

On the number of distinct minimal clique
On the number of distinct minimal clique partitions and clique covers of a line graph
✍ Sean McGuinness; Rolf Rees 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 812 KB

Let G be a line graph. Orlin determined the clique covering and clique partition numbers cc(G) and cp(G). We obtain a constructive proof of Orlin's result and in doing so we are able to completely enumerate the number of distinct minimal clique covers and partitions of G, in terms of easily calculab

A note on the line-distinguishing chroma
A note on the line-distinguishing chromatic number and the chromatic index of a graph
✍ N. Zagaglia Salvi 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 126 KB 👁 1 views

## Abstract Let λ(__G__) be the line‐distinguishing chromatic number and __x__′(__G__) the chromatic index of a graph __G__. We prove the relation λ(__G__) ≥ __x__′(__G__), conjectured by Harary and Plantholt. © 1993 John Wiley & Sons, Inc.