✦ LIBER ✦

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

✍ Scribed by Alain Billionnet

Publisher: John Wiley and Sons
Year: 1981
Tongue: English
Weight: 194 KB
Volume: 5
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190050206

No coin nor oath required. For personal study only.

✦ Synopsis

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 of another vertex y.

📜 SIMILAR VOLUMES

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

An upper bound on the ramsey number R(K3

An upper bound on the ramsey number R(K3, G) depending only on the size of the graph G

✍ A. F. Sidorenko 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 135 KB 👁 1 views

## Abstract Harary stated the conjecture that for any graph __G__ with __n__ edges and without isolated vertices __r__(__K__~3~,__G__) ⩽ 2__n__ + 1. Erdös, Faudree, Rousseau, and Schelp proved that __r__(__K__~3~,__G__) ⩽ ⌈8/3__n__⌉. Here we prove that __r__(__K__~3~,__G__) ⩽ ⌊5/2__n__⌋ −1 for __n_

The Order Upper Bound on Parity Embeddin

The Order Upper Bound on Parity Embedding of a Graph

✍ Thomas Zaslavsky 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 398 KB

A graph 1 is parity embedded in a surface if a closed path in the graph is orientation preserving or reversing according to whether its length is even or odd. The parity demigenus of 1 is the minimum of 2&/(S) (where / is the Euler characteristic) over all surfaces S in which 1 can be parity embedde

A New Upper Bound on the Cheeger Number

A New Upper Bound on the Cheeger Number of a Graph

✍ Sorin Dragomir; Elisabetta Barletta 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 117 KB

Using a technique developed by A. Nilli (1991, Discrete Math. 91, 207 210), we estimate from above the Cheeger number of a finite connected graph G of small degree (2(G) 5) admitting sufficiently distant edges. ## 2001 Academic Press Let G=(V(G), E(G)) be a finite connected graph. The Cheeger numb