✦ LIBER ✦

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

✍ Scribed by Dennis P. Geoffroy; David P. Sumner

Publisher: John Wiley and Sons
Year: 1978
Tongue: English
Weight: 308 KB
Volume: 2
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190020305

No coin nor oath required. For personal study only.

✦ Synopsis

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 satisfies ω(G) ⩽ 2|π (G)^O^|, where π(G) (the point determinant of G) is obtained from G by identifying vertices which have the same neighborhood.

📜 SIMILAR VOLUMES

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

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.

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

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

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_