On the size of graphs labeled with a condition at distance two. (English) Zbl 0848.05056

Georges, John P.; Mauro, David W.

J. Graph Theory 22, No. 1, 47-57 (1996).

A labelling of a graph \(G\) with a condition at distance two is an integer labelling of its vertices, such that labels of adjacent vertices differ by at least two, and labels of vertices at distance two in \(G\) differ by at least one. \(\lambda (G)\) is defined as the minimum difference between the smallest and largest label of any labelling of \(G\) with a condition at distance two. \({\mathcal G} (n,k)\) denotes the class of graphs with order \(n\) and \(k = \lambda (G)\). The maximum and minimum size of a graph in \({\mathcal G} (n,k)\) are investigated. Exact formulas for these maximum and minimum sizes are given, and it is also shown that for every integer \(j\) between the maximum and minimum size, there exists a graph in \({\mathcal G} (n,k)\) with this size.

Reviewer: H.Bodlaender (Utrecht)

MSC:

05C78	Graph labelling (graceful graphs, bandwidth, etc.)
05C35	Extremal problems in graph theory
05C45	Eulerian and Hamiltonian graphs

Keywords:

labelling; condition at distance two; label; size