Hostname: page-component-cd9895bd7-gvvz8 Total loading time: 0 Render date: 2024-12-26T19:07:06.696Z Has data issue: false hasContentIssue false
  • English
  • Français

Maximal Spacing Configurations in Graphs

Published online by Cambridge University Press:  01 December 1997

PETER FIRBY  and
JULIE HAVILAND
PETER FIRBY
Affiliation:
Department of Mathematics, University of Exeter, North Park Road, Exeter EX4 4QE, UK; (e-mail: [email protected])
JULIE HAVILAND
Affiliation:
Department of Mathematical Statistics and Operational Research, University of Exeter, North Park Road, Exeter EX4 4QE, UK; (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

Let G=(V, E) be a simple connected graph of order [mid ]V[mid ]=n[ges ]2 and minimum degree δ, and let 2[les ]s[les ]n. We define two parameters, the s-average distance μs(G) and the s-average nearest neighbour distance Λs(G), with respect to each of which V contains an extremal subset X of order s with vertices ‘as spread out as possible’ in G. We compute the exact values of both parameters when G is the cycle Cn, and show how to obtain the corresponding optimal arrangements of X. Sharp upper and lower bounds are then established for Λs(G), as functions of s, n and δ, and the extremal graphs described.

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 6 , Issue 4 , December 1997 , pp. 455 - 463
Copyright
1997 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)