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

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.


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