Hostname: page-component-745bb68f8f-5r2nc Total loading time: 0 Render date: 2025-02-08T09:59:29.311Z Has data issue: false hasContentIssue false
  • English
  • Français

A note on graphs with a prescribed adjacency property

Published online by Cambridge University Press:  17 April 2009

W. Ananchuen  and
L. Caccetta
W. Ananchuen
Affiliation:
School of Mathematics and Statistics Curtin University of TechnologyGPO Box U1987 Perth WA 6001, Australia
L. Caccetta
Affiliation:
School of Mathematics and Statistics Curtin University of TechnologyGPO Box U1987 Perth WA 6001, Australia
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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
Bulletin of the Australian Mathematical Society , Volume 51 , Issue 1 , February 1995 , pp. 5 - 15
Copyright
Copyright © Australian Mathematical Society 1995

References

[1]Ananchuen, W. and Caccetta, L., ‘Graphs with a prescribed adjacency property’, Austral. J. Combinatorics 6 (1992), 155–175.Google Scholar
[2]Ananchuen, W. and Caccetta, L., ‘On the adjacency properties of Paley graphs’, Networks 23 (1993), 227–236.CrossRefGoogle Scholar
[3]Ananchuen, W. and Caccetta, L., ‘On constructing graphs with a prescribed adjacency property’, Austral. J. Combinatorics (to appear).Google Scholar
[4]Blass, A., Exoo, G. and Harary, F., ‘Paley graphs satisfy all first-order adjacency axioms’, J. Graph Theory 5 (1981), 435–439.CrossRefGoogle Scholar
[5]Blass, A. and Harary, F., ‘Properties of almost all graphs and complexes’, J. Graph Theory 3 (1979), 225–240.CrossRefGoogle Scholar
[6]Bollobás, B., Random graphs (Academic Press, London, 1985).Google Scholar
[7]Bondy, J.A. and Murty, U.S.R., Graph theory with applications (The MacMillan Press, London, 1976).CrossRefGoogle Scholar
[8]Erdös, P. and Moser, L., ‘An extremal problem in graph theory’, J. Austral. Math. Soc. 11 (1970), 42–47.CrossRefGoogle Scholar
[9]Exoo, G., ‘On an adjacency property of graphs’, J. Graph Theory 5 (1981), 371–378.CrossRefGoogle Scholar
[10]Lidl, R. and Niederreiter, H., Finite fields (Addison-Wesley, London, 1983).Google Scholar
[11]Schmidt, W.M., Equations over finite fields, an elementary approach, Lecture Notes in Mathematics 536 (Springer-Verlag, Berlin, Heidelberg, New York, 1976).CrossRefGoogle Scholar