Hamiltonian Coloring on:
[Wikipedia]
[Google]
[Amazon]
Hamiltonian coloring, named after
The distance between two vertices in a graph is defined as the minimum of lengths of paths connecting those vertices. The detour distance between two vertices, say, u and v is defined as the length of the longest u-v path in the graph. In the case of a tree the detour distance between any two vertices is same as the distance between the two vertices.
William Rowan Hamilton
Sir William Rowan Hamilton Doctor of Law, LL.D, Doctor of Civil Law, DCL, Royal Irish Academy, MRIA, Royal Astronomical Society#Fellow, FRAS (3/4 August 1805 – 2 September 1865) was an Irish mathematician, astronomer, and physicist. He was the ...
, is a type of graph coloring
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices o ...
. Hamiltonian coloring uses a concept called detour distance between two vertices of the graph. It has many applications in different areas of science and technology.
Terminologies
Radio coloring
A graph G with diameter D with n nodes that is colored (i.e. has a positive integer assigned to each vertex) with k colors is called a radio k-coloring G if for every pair of vertices a and b, the sum of the distance between them and the difference between their labels ("colors") is greater than k. For example, two nodes labelled 3 and 7 with a distance of 5 is acceptable for a radio 8-coloring, but not for a radio 9-coloring, since , which is not greater than 9.Antipodal coloring
A radio (d-1)-coloring, that is, where k is equal to one less than the graph's diameter, is known as an antipodal coloring because antipodal vertices may be colored the same, but all nodes between them must be different.Detour distance
The distance between two vertices in a graph is defined as the minimum of lengths of paths connecting those vertices. The detour distance between two vertices, say, u and v is defined as the length of the longest u-v path in the graph. In the case of a tree the detour distance between any two vertices is same as the distance between the two vertices.
Hamiltonian coloring
Hamiltonian colorings are a variation on antipodal colorings where, instead of considering the regular distance between nodes, the detour distance is instead considered. Specifically, a Hamiltonian coloring's nodes have the property that the detour distance plus the difference in colors is greater than or equal to one less than n, the number of nodes in the graph. If the graph G is a path, then any Hamiltonian coloring is also an antipodal coloring, which is the inspiration for the definition of Hamiltonian coloring.References