Control and Optimization
Mohammad Alsaeedi; Mostafa Tavakolli; Ahmad Abouyee; Khatere Ghorbani Moghadam; Reza Ghanbari
Abstract
In this study, we proposed a novel graph partitioning problem where the edges are characterized by trapezoidal fuzzy numbers. A linear ranking function is employed to establish an order among these fuzzy numbers. We derive the necessary conditions for the existence of an ...
Read More
In this study, we proposed a novel graph partitioning problem where the edges are characterized by trapezoidal fuzzy numbers. A linear ranking function is employed to establish an order among these fuzzy numbers. We derive the necessary conditions for the existence of an optimal solution to this problem. To address the fuzzy graph partitioning problem, we implement and compare the performance of three algorithms: Genetic Algorithm, Tabu Search, and Sequential Least Squares Programming. The algorithms are evaluated based on objective values, computational time, and the number of iterations across multiple numerical examples. Utilizing Dolan-Moré performance profiles, we demonstrate the superiority of our proposed approach relative to existing methods. The findings highlight the robustness and computational efficiency of our methodology, making a meaningful contribution to the advancement of fuzzy graph algorithms and their practical applications.
Control and Optimization
Hanifa Mosawi; Mostafa Tavakolli; Khatere Ghorbani-Moghadam
Abstract
Graph coloring is a crucial area of research in graph theory, with numerous algorithms proposed for various types of graph coloring, particularly graph p-distance coloring. In this study, we employ a recently introduced graph coloring algorithm to develop a hybrid algorithm approximating the chromatic ...
Read More
Graph coloring is a crucial area of research in graph theory, with numerous algorithms proposed for various types of graph coloring, particularly graph p-distance coloring. In this study, we employ a recently introduced graph coloring algorithm to develop a hybrid algorithm approximating the chromatic number p-distance, where $p$ represents a positive integer number. We apply our algorithm to molecular graphs as practical applications of our findings.
Sajad Sohrabi Hesan; Freydoon Rahbarnia; Mostafa Tavakolli
Abstract
Given any graph G, its square graph G^2 has the same vertex set as G, with two vertices adjacent in G^2 whenever they are at distance 1 or 2 in G. The Cartesian product of graphs G and H is denoted by G□ H. One of the most studied NP-hard problems is the graph coloring ...
Read More
Given any graph G, its square graph G^2 has the same vertex set as G, with two vertices adjacent in G^2 whenever they are at distance 1 or 2 in G. The Cartesian product of graphs G and H is denoted by G□ H. One of the most studied NP-hard problems is the graph coloring problem. A method such as Genetic Algorithm (GA) is highly preferred to solve the Graph Coloring problem by researchers for many years. In this paper, we use the graph product approach to this problem. In fact, we prove that X((D(m',n')□D(m,n))^2)<= 10 for m,n => 3, where D(m, n) is the graph obtained by joining a vertex of the cycle C_m to a vertex of degree one of the paths P_n and X(G) is the chromatic number of the graph $G$.
Mostafa Tavakolli
Abstract
Let $S= \{e_1,\,e_2, \ldots,\,e_m\}$ be an ordered subset of edges of a connected graph $G$. The edge $S$-representation of an edge set $M\subseteq E(G)$ with respect to $S$ is the vector $r_e(M|S) = (d_1,\,d_2,\ldots,\,d_m)$, where $d_i=1$ if $e_i\in M$ and $d_i=0$ ...
Read More
Let $S= \{e_1,\,e_2, \ldots,\,e_m\}$ be an ordered subset of edges of a connected graph $G$. The edge $S$-representation of an edge set $M\subseteq E(G)$ with respect to $S$ is the vector $r_e(M|S) = (d_1,\,d_2,\ldots,\,d_m)$, where $d_i=1$ if $e_i\in M$ and $d_i=0$ otherwise, for each $i\in\{1,\ldots , k\}$. We say $S$ is a global forcing set for maximal matchings of $G$ if $r_e(M_1|S)\neq r_e(M_2|S)$ for any two maximal matchings $M_1$ and $M_2$ of $G$. A global forcing set for maximal matchings of $G$ with minimum cardinality is called a minimum global forcing set for maximal matchings, and its cardinality, denoted by $\varphi_{gm}$, is the global forcing number (GFN for short) for maximal matchings. Similarly, for an ordered subset $F = \{v_1,\,v_2, \ldots,\,v_k\}$ of $V(G)$, the $F$-representation of a vertex set $I\subseteq V(G)$ with respect to $F$ is the vector $r(I|F) = (d_1,\,d_2,\ldots,\,d_k)$, where $d_i=1$ if $v_i\in I$ and $d_i=0$ otherwise, for each $i\in\{1,\ldots , k\}$. We say $F$ is a global forcing set for independent dominatings of $G$ if $r(D_1|F)\neq r(D_2|F)$ for any two maximal independent dominating sets $D_1$ and $D_2$ of $G$. A global forcing set for independent dominatings of $G$ with minimum cardinality is called a minimum global forcing set for independent dominatings, and its cardinality, denoted by $\varphi_{gi}$, is the GFN for independent dominatings. In this paper, we study the GFN for maximal matchings under several types of graph products. Also, we present some upper bounds for this invariant. Moreover, we present some bounds for $\varphi_{gm}$ of some well-known graphs.
