Premium
On the size of graphs labeled with a condition at distance two
Author(s) -
Georges John P.,
Mauro David W.
Publication year - 1996
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(199605)22:1<47::aid-jgt7>3.0.co;2-l
Subject(s) - combinatorics , mathematics , lambda , graph , integer (computer science) , discrete mathematics , computer science , physics , optics , programming language
A labeling of graph G with a condition at distance two is an integer labeling of V (G) such that adjacent vertices have labels that differ by at least two, and vertices distance two apart have labels that differ by at least one. The lambda‐number of G , λ (G) , is the minimum span over all labelings of G with a condition at distance two. Let G ( n , k ) denote the set of all graphs with order n and lambda‐number k . In this paper, we examine the sizes of graphs in G ( n , k ). We modify Chvàtal's result on non‐hamiltonian graphs to obtain a formula for the minimum size of a graph in G ( n , k ), and we use an algorithmic approach to obtain a formula for the maximum size. Finally, we show that for any integer j between the maximum and minimum sizes there exists a graph with size j in G ( n , k ). © 1996 John Wiley & Sons, Inc.