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.
