Extremal graphs of diameter at most 6 after deleting any vertex
✍ Scribed by Yoko Usami
- Publisher
- John Wiley and Sons
- Year
- 1985
- Tongue
- English
- Weight
- 489 KB
- Volume
- 9
- Category
- Article
- ISSN
- 0364-9024
No coin nor oath required. For personal study only.
✦ Synopsis
Suppose G is a graph of n vertices and diameter at most d having the property that, after deleting any vertex, the resulting subgraph has diameter at most 6. Then G contains at least max{n. r(4n -8)/31} edges if 4 s d s 6 .
1. Introduction
We consider finite undirected simple graphs. (Terminologies not defined here can be found in 121.) The set of vertices (resp. the set of edges) of a graph G is denoted by V ( G ) (resp. E ( G ) ) . The edge joining two vertices x and y is denoted by ( x , y ) . and for subsets X ,
denotes the set of edges joining X and Y. For a vertex x in V ( G ) , the set of vertices adjacent to x is denoted by T(x) and N(.x) = T(x) u {x}.
Set deg(x)
N ( X ) = (J N ( x ) .
AEX
A subset X may be identified with the induced subgraph ( X ) , and Gu = (V(G) -u) for u E V ( C ) . For u,u in V(G), d(rr,u) denotes the distance between u and u , and d ( G ) is the diameter of G. For a real number z rzl is the least integer not less than z.