Article contents
A note on graphs with a prescribed adjacency property
Published online by Cambridge University Press: 17 April 2009
Abstract
Let m and n be nonnegative integers and k be a positive integer. A graph G is said to have property P(m, n, k) if for any set of m + n distinct vertices of G there are at least k other vertices, each of which is adjacent to the first m vertices of the set but not adjacent to any of the latter n vertices. The problem that arises is that of characterising graphs having property P(m, n, k). This problem has been considered by several authors and a number of results have been obtained. In this paper, we establish a lower bound on the order of a graph having property P(m, n, k). Further, we show that all sufficiently large Paley graphs satisfy properties P(1, n, k) and P(n, 1, k).
- Type
- Research Article
- Information
- Copyright
- Copyright © Australian Mathematical Society 1995
References
- 2
- Cited by