Change search

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) &lt; 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
Mathematics
##### Identifiers
ISI: 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

Publisher's full textScopus

#### Search in DiVA

##### By organisation
Department of Mathematics and Natural Sciences
Mathematics

doi
urn-nbn

#### Altmetric score

doi
urn-nbn
Total: 89 hits

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