Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
List graphs and distance-consistent node labelings
Blekinge Institute of Technology, Faculty of Engineering, Department of Mathematics and Natural Sciences.
Blekinge Institute of Technology, Faculty of Engineering, Department of Mathematics and Natural Sciences.
2018 (English)In: Electronic Journal of Graph Theory and Applications, ISSN 2338-2287, Vol. 6, no 1, p. 152-165Article in journal (Refereed) Published
Abstract [en]

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 Σ u,vε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. © 2018 Indonesian Combinatorics Society.

Place, publisher, year, edition, pages
INST TEKNOLOGI BANDUNG , 2018. Vol. 6, no 1, p. 152-165
Keywords [en]
Extremal combinatorics, Graph distance, Graph labeling
National Category
Mathematics
Identifiers
URN: urn:nbn:se:bth-16110DOI: 10.5614/ejgta.2018.6.1.11ISI: 000437328400011Scopus ID: 2-s2.0-85045005282OAI: oai:DiVA.org:bth-16110DiVA, id: diva2:1198941
Available from: 2018-04-19 Created: 2018-04-19 Last updated: 2018-08-20Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records BETA

Lennerstad, HåkanEriksson, Mattias

Search in DiVA

By author/editor
Lennerstad, HåkanEriksson, Mattias
By organisation
Department of Mathematics and Natural Sciences
Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 46 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf