Paths of low weight in planar graphs | Zendy

Igor Fabrici | Zendy; Jochen Harant | Zendy; Stanislav Jendrol′ | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Paths of low weight in planar graphs

Author(s) -

Igor Fabrici,

Jochen Harant,

Stanislav Jendrol′

Publication year - 2008

Publication title -

discussiones mathematicae graph theory

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.476

H-Index - 19

eISSN - 2083-5892

pISSN - 1234-3099

DOI - 10.7151/dmgt.1396

Subject(s) - mathematics , combinatorics , planar graph , induced path , path graph , planar , path (computing) , wheel graph , graph , distance , longest path problem , discrete mathematics , chordal graph , graph power , shortest path problem , line graph , computer science , computer graphics (images) , programming language

The existence of paths of low degree sum of their vertices in planar graphs is investigated. The main results of the paper are: 1. Every 3-connected simple planar graph G that contains a k-path, a path on k vertices, also contains a k-path P such that for its weight (the sum of degrees of its vertices) in G it holds wG(P ): = X u2V (P )

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research