فهرست مطالب

Communication in Combinatorics and Optimization - Volume:10 Issue: 1, Winter 2025

Communications in Combinatorics and Optimization
Volume:10 Issue: 1, Winter 2025

  • تاریخ انتشار: 1403/11/01
  • تعداد عناوین: 15
|
  • Fatemeh Raei Barandagh *, Amir Rahnamai Barghi Pages 1-19
    For any graph, Weisfeiler and  Leman assigned the smallest  matrix algebra which  contains the adjacency matrix of the graph. The coherent configuration underlying this  algebra for a graph $\Gamma$ is called the coherent configuration of $\Gamma$, denoted by $\mathcal{X}(\Gamma)$. In this paper, we study the coherent configuration of circular-arc graphs. We give a characterization of the circular-arc graphs $\Gamma$, where $\mathcal{X}(\Gamma)$  is a homogeneous coherent configuration. Moreover, all homogeneous coherent configurations which are obtained in this way are characterized as a subclass of Schurian coherent configurations.
    Keywords: Coherent Configuration, Homogeneous, Circular-Arc Graph, Wreath Product
  • Surabhi Chanda, Radha Iyer * Pages 20-56
    In 2020, mathematical chemist, Ivan Gutman, introduced a new vertex-degree-based topological index called the Sombor Index, denoted by $SO(G)$, where $G$ is a simple, connected, finite, graph. This paper aims to present some novel formulas, along with some upper and lower bounds on the Sombor Index of generalized Sierpi\'nski graphs; originally defined by Klav\v{z}ar and Milutinovi\'c by replacing the complete graph appearing in $S(n,k)$ with any graph and exactly replicating the same graph, yielding self-similar graphs of fractal nature; and on the Sombor Index of the $m$-Mycielskian or the generalized Mycielski graph; formed from an interesting construction given by Jan Mycielski (1955); of some simple graphs such as \(K_n\), \(C_n^2\), \(C_n\), and \(P_n\). We also provide Python codes to verify the results for the \(SO\left(S\left(n,K_m\right)\right)\) and \(SO\left(\mu_m\left(K_n\right)\right)\).
    Keywords: Topological Index, Sombor Index, Bounds, Sierpiński Graphs, Mycielskian Graphs
  • P. Devi, R. Rajkumar * Pages 57-68
    The complement of the intersection graph of subgroups of a group $G$, denoted by $\mathcal{I}^c(G)$, is the graph whose vertex set is the set of all nontrivial proper subgroups of $G$ and its two distinct vertices $H$ and $K$ are adjacent if and only if $H\cap K$ is trivial. In this paper, we classify all finite groups whose complement of the intersection graph of subgroups is one of totally disconnected, bipartite, complete bipartite, tree, star graph or $C_3$-free. Also we characterize all the finite groups whose complement of the intersection graph of subgroups is planar.
    Keywords: Complement Of Intersection Graph Of Subgroups, Bipartite Graph, Planar Graph
  • Razika Boutrig, Mustapha Chellali *, Nacéra Meddah Pages 69-78
    A vertex $u$ of a graph $G=(V,E)$ ve-dominates every edge incident to $u$ as well as every edge adjacent to these incident edges. A set $S\subseteq V$ is a vertex-edge dominating set (or a ved-set for short) if every edge of $E$ is ve-dominated by at least one vertex in $S$. A ved-set is independent if its vertices are pairwise non-adjacent. The independent ve-domination number $i_{ve}(G)$ is the minimum cardinality of an independent ved-set and the upper independent ve-domination number $\beta_{ve}(G)$ is the maximum cardinality of a minimal independent ved-set of $G$. In this paper, we are interesting in graphs $G$ such that $i_{ve}(G)=\beta_{ve}(G)$, which we call well ve-covered graphs. We show that recognizing well ve-covered graphs is co-NP-complete, and we present a constructive characterization of well ve-covered trees.
    Keywords: Vertex-Edge Domination, Independent Vertex-Edge Domination, Well Ve-Covered Graphs, Trees
  • Martin Knor, Riste Škrekovski, Tomáš Vetrík * Pages 79-98
    For $n \ge 2t+1$ where $t \ge 1$, the circulant graph $C_n (1, 2, \dots , t)$ consists of the vertices $v_0, v_1, v_2, \dots , v_{n-1}$ and the edges $v_i v_{i+1}$, $v_i v_{i+2}, \dots , v_i v_{i + t}$, where $i = 0, 1, 2, \dots , n-1$, and the subscripts are taken modulo $n$. We prove that the metric dimension ${\rm dim} (C_n (1, 2, \dots , t)) \ge \left\lceil \frac{2t}{3} \right\rceil + 1$ for $t \ge 5$, where the equality holds if and only if $t = 5$ and $n = 13$. Thus ${\rm dim} (C_n (1, 2, \dots , t)) \ge \left\lceil \frac{2t}{3} \right\rceil + 2$ for $t \ge 6$. This bound is sharp for every $t \ge 6$.
    Keywords: Cayley Graph, Distance, Resolving Set
  • B. Senthilkumar, M. Chellali, H. Naresh Kumar, V. Yanamandram * Pages 99-109
    An edge $e$ of a simple graph $G=(V_{G},E_{G})$ is said to ev-dominate a vertex $v\in V_{G}$ if $e$ is incident with $v$ or $e$ is incident with a vertex adjacent to $v$. A subset $D\subseteq E_{G}$ is an edge-vertex dominating set (or an evd-set for short) of $G$ if every vertex of $G$ is ev-dominated by an edge of $D$. The edge-vertex domination number of $G$ is the minimum cardinality of an evd-set of $G$. In this paper, we initiate the study of the graphs with unique minimum evd-sets that we will call UEVD-graphs. We first present some basic properties of UEVD-graphs, and then we characterize UEVD-trees by equivalent conditions as well as by a constructive method.
    Keywords: Edge-Vertex Domination, Edge-Vertex Domination Number, Trees
  • Eartha Kruft Welton, Sharif Khudairi, James Tuite * Pages 110-125
    A subset $S$ of vertices of a graph $G$ is in general position if no shortest path in $G$ contains three vertices of $S$. The general position problem consists of finding the number of vertices in a largest general position set of $G$, whilst the lower general position problem asks for a smallest maximal general position set. In this paper we determine the lower general position numbers of several families of Cartesian products. We also show that the existence of small maximal general position sets in a Cartesian product is connected to a special type of general position set in the factors, which we call a terminal set, for which adding any vertex $u$ from outside the set creates three vertices in a line with $u$ as an endpoint. We give a constructive proof of the existence of terminal sets for graphs with diameter at most three. We also present conjectures on the existence of terminal sets for all graphs and a lower bound on the lower general position number of a Cartesian product in terms of the lower general position numbers of its factors.
    Keywords: General Position Number, Universal Line, Cartesian Product
  • Jitender Kumar *, Sandeep Dalal, Pranav Pandey Pages 127-150
    The commuting graph of a finite non-commutative semigroup $S$, denoted by $\Delta(S)$, is the simple graph whose vertices are the non-central elements of $S$ and two distinct vertices $x, y$ are adjacent if $xy = yx$. In this paper, we study the commuting graph of an important class of inverse semigroups viz. Brandt semigroup $B_n$. In this connection, we obtain the automorphism group ${\rm Aut}(\Delta(B_n))$ and the endomorphism monoid End$(\Delta(B_n))$ of $\Delta(B_n)$. We show that ${\rm Aut}(\Delta(B_n)) \cong S_n \times \mathbb{Z}_2$, where $S_n$ is the symmetric group of degree $n$ and $\mathbb{Z}_2$ is the additive group of integers modulo $2$. Further, for $n \geq 4$, we prove that End$(\Delta(B_n)) = $Aut$(\Delta(B_n))$. Moreover,  we provide the vertex connectivity and edge connectivity of $\Delta(B_n)$. This paper provides a partial answer to a question posed in \cite{a.Araujo2011} and so we ascertained  a class of inverse semigroups whose commuting graph is Hamiltonian.
    Keywords: Commuting Graph, Brandt Semigroups, Automorphism Group Of A Graph
  • N. Annamalai * Pages 151-163
    In this article, we discussed the zero-divisor graph of a commutative ring with identity $\mathbb{F}_p+u\mathbb{F}_p+u^2 \mathbb{F}_p$ where $u^3=0$ and $p$ is an odd prime. We find the clique number, chromatic number, vertex connectivity, edge connectivity, diameter and girth of a zero-divisor graph associated with the ring. We find some of topological indices and the main parameters of the code derived from the incidence matrix of the zero-divisor graph $\Gamma(R).$ Also, we find the eigenvalues, energy and spectral radius  of both adjacency and Laplacian matrices of $\Gamma(R).$
    Keywords: Zero-Divisor Graph, Laplacian Matrix, Spectral Radius
  • Zahra Gharibbolooki, Sayyed Heidar Jafari * Pages 165-180
    Let $G$ be a finite group. The directed inclusion graph of cyclic subgroups of $G$, $\overrightarrow{\mathcal{I}_c}(G)$,  is the digraph with vertices of all  cyclic subgroups of $G$, and for two distinct cyclic subgroups $\langle a \rangle$ and $\langle b \rangle$, there is an arc from $\langle a\rangle $ to $\langle b\rangle $ if and only if $\langle b\rangle \subset \langle a\rangle $. The (undirected ) inclusion graph of cyclic subgroups of $G$, $\mathcal{I}_c(G)$, is the underlying graph of $\overrightarrow{\mathcal{I}_c}(G)$, that is, the vertex set is the set of all cyclic subgroups of $G$ and two distinct cyclic subgroups $\langle a \rangle$ and $\langle b \rangle$ are adjacent if and only if $\langle a\rangle \subset \langle b\rangle$ or $\langle b\rangle \subset \langle a\rangle $. In this paper, we first show that, if $G$ and $H$ are finite groups such that $\mathcal{I}_c(G)\cong \mathcal{I}_c(H)$ and $G$ is cyclic, then $H$ is cyclic. We show that for two cyclic groups $G$ and $H$ of orders $p_1^{\alpha_1} \dots  p_t^{\alpha_t}$ and $q_1^{\beta_1} \dots  q_s^{\beta_s}$, respectively, $\mathcal{I}_c(G)\cong \mathcal{I}_c(H)$ if and only if $t=s$ and by a suitable $\sigma $, $\alpha_i=\beta_{\sigma (i)}$. Also for any cyclic groups $G,~H$, if $\mathcal{I}_c(G)\cong \mathcal{I}_c(H)$, then $\overrightarrow{\mathcal{I}_c}(G) \cong \overrightarrow{\mathcal{I}_c}(H)$. We also show that for two finite abelian groups $G$ and $H$, $\mathcal{I}_c(G)\cong \mathcal{I}_c(H)$ if and only if $|\pi (G)|=|\pi (H)|$ and by a convenient permutation the graph of their sylow subgroups are isomorphic. In this case, their directed inclusion graphs are isomorphic too.
    Keywords: Inclusion Graph, Power Graph, Cyclic Subgroup, Abelian Group
  • Ghazale Asemian, Nader Jafari Rad *, Abolfazl Tehranian, Hamid Rasouli Pages 181-193
    ‎Let $r\geq 2$. A subset $S$ of vertices of a graph $G$ is a $r$-hop independent dominating set if every vertex outside $S$ is at distance $r$ from a vertex of $S$, and for any pair $v, w\in S$, $d(v, w)\neq r$. A $r$-hop Roman dominating function ($r$HRDF) is a function $f$ on $V(G)$ with values $0,1$ and $2$ having the property that for every vertex $v \in V$ with $f(v) = 0$ there is a vertex $u$ with $f(u)=2$ and $d(u,v)=r$. A $r$-step Roman dominating function ($r$SRDF) is a function $f$ on $V(G)$ with values $0,1$ and $2$ having the property that for every vertex $v$ with $f(v)=0$ or $2$, there is a vertex $u$ with $f(u)=2$ and $d(u,v)=r$. A $r$HRDF $f$ is a $r$-hop Roman independent dominating function if for any pair $v, w$ with non-zero labels under $f$, $d(v, w)\neq r$. We show that the decision problem associated with each of $r$-hop independent domination, $r$-hop Roman domination, $r$-hop Roman independent domination and $r$-step Roman domination is NP-complete even when restricted to planar bipartite graphs or planar chordal graphs.
    Keywords: Dominating Set, Hop Dominating Set, Step Dominating Set, Hop Independent Set, Hop Roman Dominating Function, Hop Roman Independent Dominating Function, Complexity
  • Shariefuddin Pirzada *, Aaqib Altaf Pages 195-206
    Let $R$ be a finite commutative ring with or without unity and $\Gamma_{e}(R)$ be its extended zero-divisor graph with vertex set $Z^{*}(R)=Z(R)\setminus \lbrace0\rbrace$ and two distinct vertices $x,y$ are adjacent if and only if $x.y=0$ or $x+y\in Z^{*}(R)$. In this paper, we characterize finite commutative rings whose extended zero-divisor graph have clique number $1 ~ \text{or}~ 2$. We completely characterize the rings of the form $R\cong R_1\times R_2 $, where $R_1$ and $R_2$ are local, having clique number $3,~4~\text{or}~5$. Further we determine the rings of the form $R\cong R_1\times R_2 \times R_3$, where $R_1$,$R_2$ and $R_3$ are local rings, to have clique number equal to six.
    Keywords: Zero-Divisor Graph, Extended Zero-Divisor Graph, Finite Commutative Rings, Clique Number
  • Seyed Morteza Mirafzal * Pages 207-217
    The folded hypercube $FQ_n$ is the Cayley graph Cay$(\mathbb{Z}_2^n,S)$, where $S=\{e_1,e_2,\dots,e_n\}\cup \{u=e_1+e_2+\dots+e_n\}$, and $e_i = (0,\dots, 0, 1, 0,$ $\dots, 0)$, with 1 at the $i$th position, $1\leq i \leq n$. In this paper, we show that the folded hypercube $FQ_n$ is a distance-transitive graph. Then, we study some properties of this graph. In particular, we show that if $n\geq 4$ is an even integer, then the folded hypercube $FQ_n$ is an $automorphic$ graph, that is, $FQ_n$ is a distance-transitive primitive graph which is not a complete or a line graph.
    Keywords: Distance-Transitive Graph, Folded Hypercube, Distance Regular Graph, Primitive Graph, Automorphic Graph
  • Kush Kumar *, Pratima Panigrahi Pages 219-231
    Let $G$ be a simple connected graph with diameter $d$, and $k\in [1,d]$ be an integer. A radio $k$-coloring of graph $G$ is a mapping $g:V(G)\rightarrow \{0\}\cup \mathbb{N}$ satisfying $\lvert g(u)-g(v)\rvert\geq 1+k-d(u,v)$ for any pair of distinct vertices $u$ and $v$ of the graph $G$, where $d(u,v)$ denotes distance between vertices $u$ and $v$ in $G$. The number ${\text{max}} \{g(u):u\in V(G)\}$ is known as the span of $g$ and is denoted by $rc_k(g)$. The radio $k$-chromatic number of graph $G$, denoted by $rc_k(G)$, is defined as $\text{min} \{rc_k(g) : g \text{ is a radio $k$-coloring of $G$}\}$. For $k=d-1$, the radio $k$-coloring of graph $G$ is called an antipodal coloring. So $rc_{d-1}(G)$ is called the antipodal number of $G$ and is denoted by $ac(G)$. Here, we study antipodal coloring of the Cartesian product of the complete graph $K_r$ and cycle $C_s$, $K_r\square C_s$, for $r\geq 4$ and $s\geq 3$. We determine the antipodal number of $K_r\square C_s$, for even $r\geq 4$ with $s\equiv 1(mod\,4)$; and for any $r\geq 4$ with $s=4t+2$, $t$ odd. Also, for the remaining values of $r$ and $s$, we give lower and upper bounds for $ac(K_r\square C_s)$.
    Keywords: Radio $K$-Coloring, Antipodal Coloring, Antipodal Number, Cartesian Product
  • Bijon Biswas, Raibatak Sen Gupta *, Mridul Kanti Sen, Sukhendu Kar Pages 232-243
    In this paper, we introduce the zero-divisor associate graph $\Gamma_D(R)$ over a finite commutative ring $R$. It is a simple undirected graph whose vertex set consists of all non-zero elements of $R$, and two vertices $a, b$ are adjacent if and only if there exist non-zero zero-divisors $z_1, z_2$ in $R$ such that $az_1=bz_2$. We determine the necessary and sufficient conditions for connectedness and completeness of $\Gamma_D(R)$ for a unitary commutative ring $R$. The chromatic number of $\Gamma_D(R)$ is also studied. Next, we characterize the rings $R$ for which $\Gamma_D(R)$ becomes a line graph of some graph. Finally, we give the complete list of graphs with at most 15 vertices which are realizable as $\Gamma_D(R)$, characterizing the associated ring $R$ in each case.
    Keywords: Zero-Divisor, Commutative Ring, Chromatic Number, Complete Graph, Line Graph