✦ LIBER ✦

A sharp upper bound for the number of stable sets in graphs with given number of cut edges

✍ Scribed by Hongbo Hua

Publisher: Elsevier Science
Year: 2009
Tongue: English
Weight: 648 KB
Volume: 22
Category: Article
ISSN: 0893-9659
DOI: 10.1016/j.aml.2009.03.011

No coin nor oath required. For personal study only.

✦ Synopsis

Let G be a connected and simple graph, and let i(G) denote the number of stable sets in G. In this letter, we have presented a sharp upper bound for the i(G)-value among the set of graphs with k cut edges for all possible values of k, and characterized the corresponding extremal graphs as well.

📜 SIMILAR VOLUMES

Maximum number of edges in connected gra

Maximum number of edges in connected graphs with a given domination number

✍ Laura A. Sanchis 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 519 KB

Sanchis, L.A., Maximum number of edges in connected graphs with a given domination number, Discrete Mathematics 87 (1991) 65-72.

A sharp edge bound on the interval numbe

A sharp edge bound on the interval number of a graph

✍ Balogh, J�zsef; Pluh�r, Andr�s 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 201 KB 👁 2 views

The interval number of a graph G, denoted by i(G), is the least natural number t such that G is the intersection graph of sets, each of which is the union of at most t intervals. Here we settle a conjecture of Griggs and West about bounding i(G) in terms of e, that is, the number of edges in G. Name

Upper bounds on the edge clique cover nu

Upper bounds on the edge clique cover number of a graph

✍ Robert C. Brigham; Ronald D. Dutton 📂 Article 📅 1984 🏛 Elsevier Science 🌐 English ⚖ 521 KB

Bounds for the genus of graphs with give

Bounds for the genus of graphs with given Betti number

✍ Martin Milgram; Peter Ungar 📂 Article 📅 1977 🏛 Elsevier Science 🌐 English ⚖ 342 KB

A new upper bound for the independence n

A new upper bound for the independence number of edge chromatic critical graphs

✍ Rong Luo; Yue Zhao 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 107 KB 👁 2 views

In 1968, Vizing conjectured that if G is a -critical graph with n vertices, then (G) ≤ n / 2, where (G) is the independence number of G. In this paper, we apply Vizing and Vizing-like adjacency lemmas to this problem and prove that (G)<(((5 -6)n) / (8 -6))<5n / 8 if ≥ 6. ᭧ 2010 Wiley

Sharp upper bounds for Zagreb indices of

Sharp upper bounds for Zagreb indices of bipartite graphs with a given diameter

✍ Shuchao Li; Minjie Zhang 📂 Article 📅 2011 🏛 Elsevier Science 🌐 English ⚖ 255 KB

For a (molecular) graph, the first Zagreb index M 1 is equal to the sum of squares of the vertex degrees, and the second Zagreb index M 2 is equal to the sum of products of the degrees of a pair of adjacent vertices. In this work, we study the Zagreb indices of bipartite graphs of order n with diame