Anwar Nsaif Jasim Inizi

On the Maximum Diameter of Graphs

Abstract— The problem of transportation is studied in many areas, most importantly in the field of logistics and operations management. The distribution problem of goods and commodities from sources to destinations is an important problem where many methods have been used to obtain its optimum solution, which represents the minimum cost of distribution the goods from sources to destinations. Generally, the transportation classical cost of one unit of a good is depending on the source and the destination. In this paper, we suggest an approach to obtain a solution to the transportation problem consisting of two products or more and then by using the modified Kruskal’s algorithm we find the minimum feasible solution.

The chessboard 8  8 is consists 64 squares. it was converted into a graph G = (V,E) with 64 vertices, which any two vertices are adjacent by edge . the problem of dominating of the chessboard Located within the subjects related to the entertainment mathematics or the puzzles in mathematics. The problem of dominating of the chessboard is to place a certain number of pieces on the chessboard. Let u , v ∈ V , u is the location of the piece and v is the location to move it , the movement of the piece of chessboard from u to v is the distance between u and v, i.e. d(u,v) =1. In this paper we applied the domination concept and total domination concept in chessboard pieces (Rook , Bishop, King , Knight and queen ) . We found graphs for each piece

Assignment models is one of topics of operations research. It consists of assigning a specific (person or worker) to a specific (task or job) assuming that there are the number of persons equal to the number of tasks available. The optimal result is to assignment one person to one job, contrast to the transportation models the source is connected to one or more of destination. The most common method to solve assignment models is the Hungarian method. In this paper introduced another method to solve assignment models by use the graph in the general formula directly. The edges are represented the cost of assigning person to task, the nods are represented the tasks and persons. The solution will be by choosing the minimum cost (edge) from the costs (edges) and delete the selected edge as well as nodes associated with the edge, then delete all other edges associated with the nodes. Repeat the process until all workers are assigned to each tasks and be the solution is the optimal solution.

This paper presents a new approach for finding a minimum feasible solution for transportation problem with different types (balanced and unbalanced). The approach is based mainly on using graph theory in general and Kruskal’s algorithm for finding Minimum Spanning Tree(MST) in finding out the first minimum cost between sources and demands. All the edges between sources and demands are sorted in an ascending order according to the weights(costs of unit delivery between sources and demands) in an array. Starting from the first element of the array which represents the absolute minimum cost, then delete either the source vertex with all its outgoing edges if this source is satisfied or deleting the targeted demand with all its incoming edges if this demand is satisfied or even both. Different examples are considered in this paper to study the correctness and the scalability of the proposed approach. The examples cover both balanced and unbalanced transportation models. As Kruskal’s algorithm works with O(E log V) time complexity, where E represents the number of edges and V is the number of vertices, however, the proposed approach tends to reduce the number of vertices and the edges after each iteration and hence it will converge faster.

Solving transportation problems where products to be supplied from one side(sources) to another (demands) with a goal to minimize the overall transportation cost represents an activity of great importance. Most of the works done in the field deals with the problem as two-sided model (Sources such as factories and Demands such as warehouses) with no connections between sources or demands. However, real world transportation problems may come in another model where sources are connected in a network like graph in which each source may supply other sources in a specific cost. The work in this paper suggests an algorithm and a graph model with mathematical solution for finding the minimum feasible solution for such widely used transportation problems. In this work, the graph representing the problem in which all sources are connected together in a network model with specific cost on each edge is converted into a new graph where additional virtual sources representing supplies between sources are added to the graph , new costs between the added sources and the demands are also calculated, and then modified Kruskal’s algorithm is applied to get the minimum feasible solution. The proposed solution is a straight forward model with strong mathematical and graph models. It can be widely used for solving real world transportation problems with feasible time and space complexity where time complexity of O(E2 + V2) is required, where E represents the number of edges and V represents the number of vertices. Different numerical examples were used to study the effectiveness and correctness of the proposed algorithm.

In this seminar, we explain how the diameter will increase after deleting some edges from graphs and calculate the exact values of the maximum diameter of an altered graph. Which is obtained by removing certain edges from some special classes of graphs, such as complete graphs, hypercube graphs, and generalized Petersen graphs. https://uokufa.edu.iq/archives/115767

1 https://mathcomp.uokufa.edu.iq/archives/12291

????? ???? ???? ??????? ?????????? ???? ??? ?????? ( ????? ??????? ?????? ?? ??????? ) ??? ???? ???????? ?????? ???? ???? ???? ?????? ??? ??????? ????????? ??? ????? ??????? ??????? ?? ???? ??????? ????? ??? ?????? ??? ?????? ???? ??? ?????? ????????? ????????? ?????? ??????? ???????????? ?? ?????? ??????.

1

1