Azarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-212810120250301On coherent configuration of circular-arc graphs1191462910.22049/cco.2023.28816.1735ENFatemeh Raei BarandaghDepartment of Mathematics Education, Farhangian University, P.O. Box 14665-889, Tehran, IranAmir Rahnamai BarghiDepartment of Mathematics, K. N. Toosi University of Technology, Tehran, IranJournal Article20230709For 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.https://comb-opt.azaruniv.ac.ir/article_14629_d9f1f125040619de623f0d486b420b49.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-212810120250301On the Sombor Index of Sierpiński and Mycielskian Graphs20561461610.22049/cco.2023.28681.1669ENSurabhi ChandaDepartment of Mathematics, Amrita School of Physical Sciences, Coimbatore, Amrita Vishwa Vidyapeetham, IndiaRadha R.IyerDepartment of Mathematics, Amrita School of Physical Sciences, Coimbatore, Amrita Vishwa Vidyapeetham, IndiaJournal Article20230526In 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)\).https://comb-opt.azaruniv.ac.ir/article_14616_37ef88f2cc871fd6f235f6b063fb86c4.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-212810120250301On the complement of the intersection graph of subgroups of a group57681461210.22049/cco.2023.28198.1476ENP. DeviDepartment of Mathematics, Sri Paramakalyani College,
Alwarkurichi - 627 412, Tamil Nadu, India.R. RajkumarDepartment of Mathematics, The Gandhigram Rural Institute (Deemed to be University),
Gandhigram - 624 302, Tamil Nadu, India0000-0001-7096-7901Journal Article20221229The 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.https://comb-opt.azaruniv.ac.ir/article_14612_0028c74365c2200f149d9f08a3c5476d.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-212810120250301Well ve-covered graphs69781462210.22049/cco.2023.28186.1469ENRazika BoutrigFaculty of Economic Sciences and Management, University of Boumerdes, AlgeriaMustapha ChellaliLAMDA-RO Laboratory, Department of Mathematics, University of Blida, B.P. 270, Blida, Algeria0000-0001-5231-6195Nacéra MeddahLAMDA-RO Laboratory, Department of Mathematics, University of Blida, B.P. 270,
Blida, AlgeriaJournal Article20221223A vertex $u$ of a graph $G=(V,E)$ <em>ve-</em>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 <em>ved-</em>set for short) if every edge of $E$ is <em>ve</em>-dominated by at least one vertex in $S$. A <em>ved</em>-set is independent if its vertices are pairwise non-adjacent. The independent <em>ve</em>-domination number $i_{ve}(G)$ is the minimum cardinality of an independent <em>ved</em>-set and the upper independent <em>ve</em>-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 <em>ve</em>-covered graphs. We show that recognizing well <em>ve</em>-covered graphs is co-NP-complete, and we present a constructive characterization of well <em>ve</em>-covered trees.https://comb-opt.azaruniv.ac.ir/article_14622_5b0120894c9fb4c0ff165e5e9a3b9f7f.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-212810120250301Sharp lower bounds on the metric dimension of circulant graphs79981467910.22049/cco.2023.28792.1725ENMartin KnorSlovak University of Technology, Bratislava, SlovakiaRiste ŠkrekovskiFaculty of Mathematics and Physics, University of Ljubljana, Ljubljana, SloveniaFaculty of Information Studies, Novo Mesto, SloveniaTomáš VetríkDepartment of Mathematics and Applied Mathematics, University of the Free State,
Bloemfontein, South AfricaJournal Article20230627For $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$.https://comb-opt.azaruniv.ac.ir/article_14679_29912c4a1254e5c2c996b712fa484797.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-212810120250301Graphs with unique minimum edge-vertex dominating sets991091462410.22049/cco.2023.28605.1631ENB. SenthilkumarDepartment of Mathematics,
SASTRA Deemed to be University,
Thanjavur, Tamil Nadu, India0000-0001-8121-7233M. ChellaliLAMDA-RO Laboratory, Department of Mathematics, University of Blida, B.P. 270, Blida, Algeria0000-0001-5231-6195H. Naresh KumarDepartment of Mathematics,
SASTRA Deemed to be University,
Thanjavur, Tamil Nadu, India0000-0002-1717-239XV. B.YanamandramDepartment of Mathematics,
SASTRA Deemed to be University,
Thanjavur, Tamil Nadu, India0000-0003-4560-2040Journal Article20230427An edge $e$ of a simple graph $G=(V_{G},E_{G})$ is said to <em>ev</em>-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 <em>evd-set</em> for short) of $G$ if every vertex of $G$ is <em>ev</em>-dominated by an edge of $D$. The edge-vertex domination number of $G$ is the minimum cardinality of an <em>evd-set</em> of $G$. In this paper, we initiate the study of the graphs with unique minimum <em>evd-sets</em> 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.https://comb-opt.azaruniv.ac.ir/article_14624_eae8f8a567652a62665160d11fe2edf1.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-212810120250301Lower General Position in Cartesian Products1101251476310.22049/cco.2024.29171.1879ENEartha Kruft WeltonSchool of Mathematics and Statistics, Open University, Milton Keynes, UKSchool of Mathematics, University of Cardiff, UKSharif KhudairiSchool of Mathematics, University of Cardiff, UKJames TuiteSchool of Mathematics and Statistics, Open University, Milton Keynes, UK0000-0003-2604-7491Journal Article20231110A 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.https://comb-opt.azaruniv.ac.ir/article_14763_b2641014b8ac6cf88ea5c565f2371e6e.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-212810120250301Commuting graph of an aperiodic Brandt Semigroup1271501462710.22049/cco.2023.27768.1349ENJitender KumarDepartment of Mathematics, Birla Institute of Technology and Science Pilani, Pilani-333031, IndiaSandeep DalalSchool of Mathematical Sciences, National Institute of Science Education and Research,
Bhubaneswar, Odisha 752050, IndiaPranav PandeyDepartment of Mathematics, Birla Institute of Technology and Science Pilani, Pilani-333031, IndiaJournal Article20220412The 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.https://comb-opt.azaruniv.ac.ir/article_14627_c1097897f83499a7ec429c7b6476b27b.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-212810120250301On Zero-Divisor Graph of the ring $\mathbb{F}_p+u\mathbb{F}_p+u^2 \mathbb{F}_p$1511631464110.22049/cco.2023.28238.1486ENN. AnnamalaiDepartment of Basic Engineering, Lecturer in Mathematics, Government Polytechnic College,
Sankarapuram, Kallakurichi-606401, Tamil Nadu, India0000-0002-9507-8569Journal Article20230110In 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).$https://comb-opt.azaruniv.ac.ir/article_14641_e345ddae4bbd7fc738aff7bac434528d.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-212810120250301Finite Abelian Groups with Isomorphic Inclusion Graphs of Cyclic Subgroups1651801463010.22049/cco.2023.27806.1356ENZahra GharibbolookiFaculty of Mathematical Science, Shahrood University of Technology, Shahrood, I.R. IranSayyed Heidar JafariFaculty of Mathematical Science, Shahrood University of Technology, Shahrood, I.R. IranJournal Article20220512Let $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.https://comb-opt.azaruniv.ac.ir/article_14630_a1c05e26b27196477f43dcd1e40ecbbc.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-212810120250301NP-completeness of some generalized hop and step domination parameters in graphs1811931465310.22049/cco.2023.28699.1676ENGhazale AsemianDepartment of Mathematics, Science and Research Branch, Islamic Azad University, Tehran, IranNader Jafari RadDepartment of Mathematics, Shahed University, Tehran, IranAbolfazl TehranianDepartment of Mathematics, Science and Research Branch, Islamic Azad University, Tehran, IranHamid RasouliDepartment of Mathematics, Science and Research Branch, Islamic Azad University, Tehran, IranJournal Article20230531Let $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.https://comb-opt.azaruniv.ac.ir/article_14653_627e12c1abb6cd8995a87262f8065bf8.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-212810120250301Cliques in the extended zero-divisor graph of finite commutative rings1952061465110.22049/cco.2023.28740.1693ENShariefuddin PirzadaDepartment of Mathematics, University of Kashmir, Srinagar, India0000-0002-1137-517XAaqib AltafDepartment of Mathematics, Lovely Professional University, Punjab, IndiaJournal Article20230611Let $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.https://comb-opt.azaruniv.ac.ir/article_14651_59ed0dc4aa23eb078b9331b9dfc309f6.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-212810120250301On the distance-transitivity of the folded hypercube2072171465610.22049/cco.2023.28704.1679ENSeyed Morteza MirafzalDepartment of Mathematics, Faculty of Basic Science, Lorestan University,
Khorramabad, Iran0000-0002-3545-7022Journal Article20230601The folded hypercube $FQ_n$ is the Cayley graph Cay$(\mathbb{Z}_2^n,S)$, where $S=\{e_1,e_2,\dots,e_n\}\cup <br />\{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.https://comb-opt.azaruniv.ac.ir/article_14656_78491c62c325cd731571e4541bce6a62.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-212810120250301Antipodal Number of Cartesian Product of Complete Graphs with Cycles2192311464310.22049/cco.2023.28693.1674ENKush KumarDepartment of Mathematics, Indian Institute of Technology,
Kharagpur, 721302, West Bengal, IndiaPratima PanigrahiDepartment of Mathematics, Indian Institute of Technology,
Kharagpur, 721302, West Bengal, IndiaJournal Article20230530Let $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)$.https://comb-opt.azaruniv.ac.ir/article_14643_752d59adbdbc4ab594abccd7caadca65.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-212810120250301The zero-divisor associate graph over a finite commutative ring2322431465510.22049/cco.2023.28488.1577ENBijon BiswasDepartment of Science and Humanities, Ranaghat Government Polytechnic,
Nadia - 741201, WB, IndiaRaibatak Sen GuptaDepartment of Mathematics, Bejoy Narayan Mahavidyalaya, West Bengal-712147, IndiaMridul Kanti SenDepartment of Pure Mathematics, University of Calcutta, Kolkata - 700019, IndiaSukhendu KarDepartment of Mathematics, Jadavpur University, Kolkata - 700032, India0000-0002-3955-9464Journal Article20230326In 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.https://comb-opt.azaruniv.ac.ir/article_14655_1c9367e7e91053c0c9d2b413a822acd7.pdf