Locating-coloring on Halin graphs with a certain number of inner faces

For any tree T with at least four vertices and no vertices of degree two, define a Halin graph H(T) as a planar graph constructed from an embedding of T in a plane by connecting all the leaves (the vertices of degree 1) of T to form a cycle C that passes around T in the natural cyclic order defined...

Full description

Saved in:
Bibliographic Details
Main Authors: Purwasih, I. A., Baskoro, E. T., Assiyatun, H., Suprijanto, D.
Format: Conference Proceeding
Language:English
Subjects:
Coloring
Construction planning
Dynamic programming
Embedding
Graph theory
Graphs
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:For any tree T with at least four vertices and no vertices of degree two, define a Halin graph H(T) as a planar graph constructed from an embedding of T in a plane by connecting all the leaves (the vertices of degree 1) of T to form a cycle C that passes around T in the natural cyclic order defined by the embedding of T . The study of the properties of a Halin graph has received much attention. For instances, it has been shown that every Halin graph is 3-connected and Hamiltonian. A Halin graph has also treewidth at most three, so that many graph optimization problems that are NP-complete for arbitrary planar graphs may be solved in linear time on Halin graphs using dynamic programming. In this paper, we characterize all Halin graphs with 3,4,5,6, and 7 inner faces and give their locating-chromatic number. Furthermore, we show that there exist a Halin graph having locating-chromatic number k ≥ 4 with r ≥ max { 3 , ( k − 2 ) 3 − ( k − 2 ) 2 2 + 1 } inner faces.
ISSN:0094-243X
1551-7616
DOI:10.1063/1.4940815