Article Per Year (5 Year)
p-Index From 2019 - 2024
0
P-Index
This Author published in this journals
All Journal Electronic Journal of Graph Theory and Applications (EJGTA)
Mattias Eriksson
Dept. of Mathematics and Science, Blekinge Institute of Technology, S-37179 Sweden
Electrical & Electronics Engineering

Published : 1 Documents Claim Missing Document
Claim Missing Document
Check
Articles

Found 1 Documents
Search

 1 
List graphs and distance-consistent node labelings Håkan Lennerstad; Mattias Eriksson
Electronic Journal of Graph Theory and Applications (EJGTA) Vol 6, No 1 (2018): Electronic Journal of Graph Theory and Applications
Publisher : GTA Research Group, Univ. Newcastle, Indonesian Combinatorics Society and ITB

Show Abstract | Download Original | Original Source | Check in Google Scholar | DOI: 10.5614/ejgta.2018.6.1.11

Abstract

In this paper we consider node labelings c of an undirected connected graph G = (V, E) with labels {1, 2, ..., ∣V∣}, which induce a list distance c(u, v) = ∣c(v) − c(u)∣ besides the usual graph distance d(u, v). Our main aim is to find a labeling c so c(u, v) is as close to d(u, v) as possible. For any graph we specify algorithms to find a distance-consistent labeling, which is a labeling c that minimize $\sum\limits_{u,v\in V} (c(u,v)-d(u,v)) ^2$. Such labeliings may provide structure for very large graphs. Furthermore, we define a labeling c fulfilling d(u1, v1) < d(u2, v2) ⇒ c(u1, v1) ≤ c(u2, v2) for all node pairs u1, v1 and u2, v2 as a list labeling, and a graph that has a list labeling is a list graph. We prove that list graphs exist for all n = ∣V∣ and all k = ∣E∣ : n − 1 ≤ k ≤ n(n − 1)/2, and establish basic properties. List graphs are hamiltonian, and show weak versions of properties of path graphs.
Co-Authors Håkan Lennerstad