Graph labeling is a topic in graph theory that is developing very rapidly because of its application in various fields, for example in coding theory, X-ray crystallography, address systems on networks, circuit design, transportation, database relations, radio frequency determination, etc. In general, graph labeling is the assignment of labels (usually integers) to the elements of a graph (vertices and/or edges). If a label is assigned to each vertex, then the labeling is called vertex labeling. Meanwhile, if the labeling is given on each edge, the labeling is called edge labeling. If labeling is given to each vertex and edge, then the labeling is called total labeling.

Network addressing using super edge magic total labeling


Graph coloring is one of the optimization problems for research in the field of Graph Theory. This coloring problem starts with coloring maps of countries such that no two bordering countries have the same color. This phenomenon is then represented in the form of a planar graph (a graph which, if drawn in a plane, does not have edges crossing) with the country as the vertex and the border as the edge. Furthermore, this problem is known as the Four Color Problem which states that every planar graph can be colored using four colors.

Solving sudoku puzzle using vertex coloring

Vertex coloring in a graph is the assignment of color to each vertex so that two adjacent vertices must have a different color and the number of colors used must be as minimal as possible. Graph coloring is not only done for vertices, but also for edges. Edge coloring is defined as follows. Given a graph G, edge coloring on a graph G is coloring the edges of G in such a way that no two adjacent edges (ending at the same vertex) receive the same color. The graph coloring problem is used as a model in various applications such as scheduling systems, frequency allocation, sudoku puzzles and so on.


The topology of a computer network is usually studied using Graph Theory instruments, in which a network is represented by a graph consisting of a set of vertices, and some or all possible pairs of vertices connected by edges. Each node is represented by a vertex, and two vertices are connected by an edge if there is a bidirectional relationship between the two nodes. If the relationship is only one way, then the two vertices are connected by an arc (directed edge).

Computer network topology

Among a number of factors considered in the design of computer networks, there are two factors that appear most often, namely (1) the number of connections that can be connected to a computer is limited, and (2) the communication route between any two computers is as short as possible. The ultimate goal is to produce a large computer network (as many computers as possible) with two limitations that have been given. In graph theory terms, this problem is called the degree/diameter problem, namely: How to construct a graph with as many vertices as possible, if the given degree is the maximum ∆ and the diameter is k?


The dominating set is one of the topics in Graph Theory which was first introduced by Berge in 1958. The domination set in a graph has various applications, including computer communication networks, social networks, CCTV camera placement, survey location determination, inter bus placement. pick up, and so on. This chapter presents the concept of domination sets and the results of their development for distances of more than one, namely distance domination sets.

CCTV placement using dominating set


Metric dimension is one of the topics in Graph Theory which is built from Linear Algebra, namely the concepts of basis and dimension. This concept was developed by Harary in 1976. The basis of a graph is the set of vertices with the least cardinality which makes each vertex in the graph have a different representation of that basis. The representation of these points uses the concept of distance (metric) between points in the graph, in order to obtain the metric dimension which is the cardinality of the basis in the graph. The metric dimension is usually used for various applications such that robot navigation.

Robot navigation using metric dimension