A note on harmonic subgraphs in labelled geometric graphs

G. Araujo; J. Balogh; R. Fabila; G. Salazar; J. Urrutia

doi:10.1016/j.ipl.2007.08.016

A note on harmonic subgraphs in labelled geometric graphs

G. Araujo
, J. Balogh
, R. Fabila
, G. Salazar
, J. Urrutia

Mathematics

Research output: Contribution to journal › Article › peer-review

Abstract

Let S be a set of n points in general position in the plane, labelled bijectively with the integers {0, 1, ..., n - 1}. Each edge (the straight segment that joins two points) is labelled with the sum of the labels of its endpoints. In this note we investigate the maximum size of noncrossing matchings and paths on S, under the requirement that no two edges have the same weight.

Original language	English (US)
Pages (from-to)	98-102
Number of pages	5
Journal	Information Processing Letters
Volume	105
Issue number	3
DOIs	https://doi.org/10.1016/j.ipl.2007.08.016
State	Published - Jan 31 2008

Keywords

Computational geometry
Graceful labellings
Harmonic subgraphs

ASJC Scopus subject areas

Theoretical Computer Science
Signal Processing
Information Systems
Computer Science Applications

Online availability

10.1016/j.ipl.2007.08.016

Library availability

Discover UIUC Full Text

Cite this

@article{390d1e011a1e4d808a7b41fde9eb9c2d,

title = "A note on harmonic subgraphs in labelled geometric graphs",

abstract = "Let S be a set of n points in general position in the plane, labelled bijectively with the integers \{0, 1, ..., n - 1\}. Each edge (the straight segment that joins two points) is labelled with the sum of the labels of its endpoints. In this note we investigate the maximum size of noncrossing matchings and paths on S, under the requirement that no two edges have the same weight.",

keywords = "Computational geometry, Graceful labellings, Harmonic subgraphs",

author = "G. Araujo and J. Balogh and R. Fabila and G. Salazar and J. Urrutia",

note = "* Corresponding author. E-mail addresses: [email protected] (G. Araujo), [email protected] (J. Balogh), [email protected] (R. Fabila), [email protected] (G. Salazar), [email protected] (J. Urrutia). 1 Supported by Grant PAPIIT IN106305-3. 2 Supported by NSF Grant DMS-0302804. 3 Supported by FAI-UASLP and by CONACYT Grant 45903. 4 Supported by CONACYT Grant 45876.",

year = "2008",

month = jan,

day = "31",

doi = "10.1016/j.ipl.2007.08.016",

language = "English (US)",

volume = "105",

pages = "98--102",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "3",

}

TY - JOUR

T1 - A note on harmonic subgraphs in labelled geometric graphs

AU - Araujo, G.

AU - Balogh, J.

AU - Fabila, R.

AU - Salazar, G.

AU - Urrutia, J.

N1 - * Corresponding author. E-mail addresses: [email protected] (G. Araujo), [email protected] (J. Balogh), [email protected] (R. Fabila), [email protected] (G. Salazar), [email protected] (J. Urrutia). 1 Supported by Grant PAPIIT IN106305-3. 2 Supported by NSF Grant DMS-0302804. 3 Supported by FAI-UASLP and by CONACYT Grant 45903. 4 Supported by CONACYT Grant 45876.

PY - 2008/1/31

Y1 - 2008/1/31

N2 - Let S be a set of n points in general position in the plane, labelled bijectively with the integers {0, 1, ..., n - 1}. Each edge (the straight segment that joins two points) is labelled with the sum of the labels of its endpoints. In this note we investigate the maximum size of noncrossing matchings and paths on S, under the requirement that no two edges have the same weight.

AB - Let S be a set of n points in general position in the plane, labelled bijectively with the integers {0, 1, ..., n - 1}. Each edge (the straight segment that joins two points) is labelled with the sum of the labels of its endpoints. In this note we investigate the maximum size of noncrossing matchings and paths on S, under the requirement that no two edges have the same weight.

KW - Computational geometry

KW - Graceful labellings

KW - Harmonic subgraphs

UR - https://www.scopus.com/pages/publications/36549023878

UR - https://www.scopus.com/pages/publications/36549023878#tab=citedBy

U2 - 10.1016/j.ipl.2007.08.016

DO - 10.1016/j.ipl.2007.08.016

M3 - Article

AN - SCOPUS:36549023878

SN - 0020-0190

VL - 105

SP - 98

EP - 102

JO - Information Processing Letters

JF - Information Processing Letters

IS - 3

ER -

A note on harmonic subgraphs in labelled geometric graphs

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this