𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the adjacency properties of paley graphs

✍ Scribed by W. Ananchuen; L. Caccetta

Publisher
John Wiley and Sons
Year
1993
Tongue
English
Weight
614 KB
Volume
23
Category
Article
ISSN
0028-3045

No coin nor oath required. For personal study only.

✦ Synopsis

In the application of graph theory to problems arising in network design, the requirements of the network can be expressed in terms of restrictions on the values of certain graph parameters such as connectivity, edge-connectivity, diameter, and independence number. In this paper, we focus on networks whose requirements translate into adjacency restrictions on the graph representing the network. More specifically, a graph G is said to have property P(m,n,k) if for any set of m + n distinct vertices there are at least k other vertices, each of which is adjacent to the first m vertices but not adjacent to any of the latter n vertices. The problem that arises is that of characterizing graphs having property P(m,n,k). In this paper, we present properties of graphs satisfying the adjacency property. In particular, for 9 = l(mod 4), a prime power, the Paley graph G, of order 9 is the graph whose vertices are elements of the finite field I F, ; two vertices are adjacent if and only if their difference is a quadratic residue. For any m, n , and k , we show that all sufficiently large Paley graphs satisfy P(m,n,k). 0 7993 by John Wiley & Sons, Inc.

πŸ“œ SIMILAR VOLUMES

On an adjacency property of graphs
On an adjacency property of graphs
✍ Geoffrey Exoo πŸ“‚ Article πŸ“… 1981 πŸ› John Wiley and Sons 🌐 English βš– 374 KB

## Abstract A graph __G__ has property __A(m, n, k)__ if for any sequence of __m__ + __n__ distinct points of __G__, there are at least __k__ other points, each of which is adjacent to the first __m__ points of the sequence but not adjacent to any of the latter __n__ points. the minimum order among

The smallest graphs with certain adjacen
The smallest graphs with certain adjacency properties
✍ Geoffrey Exoo; Frank Harary πŸ“‚ Article πŸ“… 1980 πŸ› Elsevier Science 🌐 English βš– 758 KB

A graph is said to have property Pi,, if for every sequence of n + 1 points, there is another point adjacent only to the first point. It has previously been shown that almost all graphs have property Pi,,. It is easy to verify that for each n, there is a cube with this property. A more delicate ques

Graphs with the n-e.c. adjacency propert
Graphs with the n-e.c. adjacency property constructed from resolvable designs
✍ Catharine A. Baker; Anthony Bonato; Neil A. McKay; PaweΕ‚ PraΕ‚at πŸ“‚ Article πŸ“… 2009 πŸ› John Wiley and Sons 🌐 English βš– 144 KB

## Abstract Only recently have techniques been introduced that apply design theory to construct graphs with the __n__‐e.c. adjacency property. We supply a new random construction for generating infinite families of finite regular __n__‐e.c. graphs derived from certain resolvable Steiner 2‐designs.

Characterizations of adjacency on the br
Characterizations of adjacency on the branching polyhedron
✍ Rick Giles; Dirk Hausmann πŸ“‚ Article πŸ“… 1979 πŸ› Elsevier Science 🌐 English βš– 805 KB

Given two distinct branchings of a directed graph G, we present several conditions which are equivalent to the corresporiding incidence vectors of the branchings being adjacent on the branching polyhedron of 6. The proof of these equivalences uses a "shrinking algorithm'\* whi\_h will determine in O

Characterization of a class of triangle-
Characterization of a class of triangle-free graphs with a certain adjacency property
✍ Brian Alspach; C. C. Chen; Katherine Heinrich πŸ“‚ Article πŸ“… 1991 πŸ› John Wiley and Sons 🌐 English βš– 597 KB

## Abstract Let __m__ and __n__ be nonnegative integers. Denote by __P__(__m,n__) the set of all triangle‐free graphs __G__ such that for any independent __m__‐subset __M__ and any __n__‐subset __N__ of __V__(__G__) with __M__ ∩ __N__ = Ø, there exists a unique vertex of __G__ that is adjacent to e