Graph labeling deals with the assignment of integers to the vertices or edges of the graph. In this thesis, linear arrangement and graceful labeling which are well-known graph labeling problems are investigated. Also several new graph labeling problems are proposed and investigated. The problems are motivated from various problems of practical interest and approached from a viewpoint of graph labeling.
First, we introduce a new graph labeling problem called d-edge labeling. The constraint in this labeling is placed on the allowable edge label which is the difference between the labels of endvertices of an edge. Each edge label should be a power of d. We show that every full quaternary tree admits 2-edge labeling and every full binary tree and binomial tree admits 4-edge labeling by giving labeling schemes to them. The labelings on the trees are applied to their embeddings into hypercubes and recursive circulants.
Second, we show that min-sum and min-cut linear arrangement problems on trees can be represented as path labeling problem on trees. In a path labeling of a tree, we successively find paths in the tree and assign labels to the edges of each path. The labels assigned to edges are used to find a linear arrangement satisfying some conditions. As an application of the path labeled tree, two-row arrangement problem is considered. The problem is to minimize the crossing number of the edges when the vertices of a tree are placed in two rows and the edges are connected by straight lines. A formula on the crossing number of two-row arrangement obtained from a path labeled tree is given in terms of the cost of the path labeling. Also the relation between the min-sum path labeling of a tree and the optimal two-row arrangement of the tree is investigated.
Third, we propose transitive labeling on comparability graphs. A new expression on the cost of a linear arrangement is derived. And we show that a transitive labeling on the comparability graph minimizes a term in the cost expression. The term is concerned with the complement graph of a comparability graph, which is called cocomparability graph. Based on the transitive labeling, we present an approximation algorithm for the min-sum linear arrangements of cocomparability graphs. Cocomparability graphs are a class of perfect graphs, and contain interval graphs and permutation graphs which have a large number of applications. And the algorithm leads to simple algorithms provided that the interval representation of an interval graph or the permutation corresponding to a permutation graph is given.
Finally, new class of graceful graphs are presented. The graphs can be represented by graph join operations and have relatively large number of edges to the number of vertices. The graphs are included in the class of graphs that is obtained by graph join of star tree and graceful tree, join of cycle and null graph, and join of complete bipartite graph and null graph.
그래프의 번호매김은 그래프의 정점이나 에지에 정수를 할당하는 것을 말한다. 본 논문에서는 널리 알려진 번호매김 문제인 선형배열과 graceful 번호매김에 대해 연구하였고 또한 몇가지 새로운 번호매김 문제들을 제안하고 연구하였다. 제안된 문제들은 실제적인 응용분야에서 얻어진 문제들로서 그래프의 번호매김의 관점에서 접근되었다.
먼저 새로운 번호매김 문제로서 d-에지 번호매김 문제를 제안하고 연구하였다. 이 문제는 주어진 그래프의 정점에 대한 번호매김중, 에지번호를 양끝 정점에 할당된 정수값의 차이로 정의할때, 각 에지번호가 d의 거듭제곱이 되는 것을 찾기위한 문제이다. 모든 완전 4진 트리에 대한 2-에지번호매김 방법과, 모든 완전 이진트리와 이항트리에 대한 4-에지 번호매김 방법을 제시하였다. 그리고 그 결과를 네트워크 구조인 재귀원형군과 하이퍼큐브에 대한 트리 embedding에 응용하였다.
다음으로 트리에 대한 최소 선형배열과 최소자름 선형배열 문제가 트리의 경로에 대한 번호매김 문제로 나타낼수 있음을 보였다. 그리고 경로에 대한 번호매김의 응용으로서 트리의 이분할된 정점들을 두개의 행에 배열하였을때 에지들의 교차점의 갯수를 최소화 하기 위한 이행배열 문제를 연구하였다. 경로에 번호매김된 트리를 이행배열로 변환하는 방법을 제시하고, 트리의 최소 경로 번호매김으로부터 최적 이행배열을 얻을수 있음을 보였다.
또한 비교그래프에 대한 이행성 번호매김 문제를 제안하고 연구하였다. 선형배열의 비용에 대한 새로운 형태의 수식을 유도하고 이행성 번호매김이 그 수식에 있어서 한 항을 최소화 함을 보였다. 그 항은 비교그래프의 보그래프인 보비교그래프와 관계가 있다. 보비교그래프는 완벽그래프의 일종으로서 구간그래프나 순열그래프를 포함하고 있다. 이행성 번호매김에 의거해 보비교그래프의 최소 선형배열에 대한 근사 알고리즘을 제시하였다. 제시된 근사 알고리즘은 구간그래프에 해당하는 구간의 집합이나 순열그래프에 해당하는 순열이 주어진 경우에 있어서는 더욱 간단한 알고리즘에 의해 구현될수 있음을 보였다. 그리고 순열그래프에 있어서 제시된 근사 알고리즘을 실행한 결과를 통해 성능평가를 하였다.
마지막으로, 새로운 부류의 graceful 그래프들을 제시하였다. 제시된 그래프들은 그래프 join 연산에 의해 얻어지는 것들로서 정점의 갯수에 비해 에지수가 비교적 많은 것들이다. 제시된 graceful 그래프들은 성형 트리와 graceful 트리, 싸이클과 null 그래프, 그리고 완전 이분 그래프와 null 그래프의 join에 의해 얻을수 있는 그래프의 부류에 속한다.
