✦ LIBER ✦

An upper bound on the sum of squares of degrees in a graph

✍ Scribed by D. de Caen

Publisher: Elsevier Science
Year: 1998
Tongue: English
Weight: 163 KB
Volume: 185
Category: Article
ISSN: 0012-365X
DOI: 10.1016/s0012-365x(97)00213-6

No coin nor oath required. For personal study only.

✦ Synopsis

Let G be a simple graph with n vertices, e edges and vertex degrees &, d2 ..... d~. It is proved that d2+ ... +d~<~e(2e/(n-1)+ n-2) when n~>2. This bound does not generalize to all sequences of positive integers. A comparison is made to another upper bound on d 2 +. • -+ d 2, due to Sz6kely et al. (1992). Our inequality follows from the positive semidefiniteness of a certain quadratic form in (2) variables. We also apply the inequality to bounding the total number of triangles in a graph and its complement. (~

📜 SIMILAR VOLUMES

Upper bounds on the sum of powers of the

Upper bounds on the sum of powers of the degrees of a simple planar graph

✍ Jochen Harant; Stanislav Jendrol; Tomáš Madaras 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 131 KB 👁 1 views

An upper bound on the number of cliques

An upper bound on the number of cliques in a graph

✍ Martin Farber; Mihály Hujter; Zsolt Tuza 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 252 KB 👁 1 views

On an upper bound of a graph's chromatic

On an upper bound of a graph's chromatic number, depending on the graph's degree and density

✍ O.V Borodin; A.V Kostochka 📂 Article 📅 1977 🏛 Elsevier Science 🌐 English ⚖ 159 KB

An upper bound on the size of a largest

An upper bound on the size of a largest clique in a graph

✍ Dennis P. Geoffroy; David P. Sumner 📂 Article 📅 1978 🏛 John Wiley and Sons 🌐 English ⚖ 308 KB 👁 1 views

## Abstract A graph is point determining if distinct vertices have distinct neighborhoods. The nucleus of a point‐determining graph is the set __G__^O^ of all vertices, __v__, such that __G__–__v__ is point determining. In this paper we show that the size, ω(__G__), of a maximum clique in __G__ sat

An upper bound on the size of the larges

An upper bound on the size of the largest cliques in a graph

✍ Alain Billionnet 📂 Article 📅 1981 🏛 John Wiley and Sons 🌐 English ⚖ 194 KB 👁 1 views

## Abstract We produce in this paper an upper bound for the number of vertices existing in a clique of maximum cardinal. The proof is based in particular on the existence of a maximum cardinal clique that contains no vertex __x__ such that the neighborhood of __x__ is contained in the neighborhood

On an upper bound for the harmonious chr

On an upper bound for the harmonious chromatic number of a graph

✍ Zhikang Lu 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 125 KB 👁 2 views

## Abstract The upper bound for the harmonious chromatic number of a graph that has been given by Sin‐Min Lee and John Mitchem is improved.