فهرست مطالب

Communication in Combinatorics and Optimization - Volume:10 Issue: 3, Summer 2025

Communications in Combinatorics and Optimization
Volume:10 Issue: 3, Summer 2025

  • تاریخ انتشار: 1403/11/14
  • تعداد عناوین: 16
|
  • Djoko Suprijanto *, Hopein Tang Pages 497-517
    In this work, we study a class of skew cyclic codes over the ring $R:=\mathbb{Z}_4+v\mathbb{Z}_4,$ where $v^2=v,$ with an automorphism $\theta$ and a derivation $\Delta_\theta,$ namely codes as modules over a skew polynomial ring $R[x;\theta,\Delta_{\theta}],$ whose multiplication is defined using an automorphism $\theta$ and a derivation $\Delta_{\theta}.$ We investigate the structures of a skew polynomial ring $R[x;\theta,\Delta_{\theta}].$ We define $\Delta_{\theta}$-cyclic codes as a generalization of the notion of cyclic codes. The properties of $\Delta_{\theta}$-cyclic codes as well as dual $\Delta_{\theta}$-cyclic codes are derived. As an application, some new linear codes over $\mathbb{Z}_4$ with good parameters are obtained by Plotkin sum construction, also via a Gray map as well as residue and torsion codes of these codes.
    Keywords: Cyclic Codes, Quasi-Cyclic Codes, Skew Polynomial Ring, Skew Cyclic Codes, Derivation
  • M.R. Raksha, Charles Dominic * Pages 519-530
    The zero forcing number of a graph is the minimum cardinality among all the zero forcing sets of a graph $G$.  The aim of this article is to compute the zero forcing number of complementary prism graphs.  Some bounds on the zero forcing number of complementary prism graphs are presented. The remainder of this article discusses the following result.  Let $G$ and $\overline{G }$ be connected graphs. Then $Z(G\overline{G})\leq n-1$ if and only if  there exists two vertices $v_i,v_j \in V(G)$ and $i\neq j$ such that, either $N(v_i) \subseteq N(v_j)$ or $N[v_i] \subseteq N[v_j]$ in $G$.
    Keywords: Zero Forcing Set, Zero Forcing Number, Complementary Prism Graph
  • H. Abdollahzadeh Ahangar *, H. Rahbani, M.R. Sadeghi Pages 531-537
    A Roman dominating function (or just \textit{RDF}) on a graph $G =(V, E)$ is a function $f: V \longrightarrow \{0, 1, 2\}$ satisfying the condition that every vertex $u$ for which $f(u) = 0$ is adjacent to at least one vertex $v$ for which $f(v) = 2$. The weight of an \textit{RDF} $f$ is the value $f(V)=\sum_{u \in {V}}f(u)$. An \textit{RDF} $f$ can be represented as $f=(V_0,V_1,V_2)$, where $V_i=\{v\in V:f(v)=i\}$ for $i=0,1,2$. An \textit{RDF} $f=(V_0,V_1,V_2)$ is called a locating Roman dominating function (or just \textit{L\textit{RDF}}) if $N(u)\cap V_2\neq N(v)\cap V_2$ for any pair $u,v$ of distinct vertices of $V_0$. The locating-Roman domination number $\gamma_R^L(G)$ is the minimum weight of an \textit{L\textit{RDF}} of $G$. A graph $G$ is said to be a locating Roman domination edge  critical graph, or just $\gamma_R^L$-edge critical graph, if $\gamma_R^L(G-e)>\gamma_R^L(G)$ for all $e\in E$. The purpose of this paper is to characterize the class of $\gamma_R^L$-edge critical graphs.
    Keywords: Roman Domination, Locating Roman Domination Number, Critical Graph
  • Nasrin Dehgardi * Pages 539-545
    For a graph $\Gamma$‎, ‎the re-defined third Zagreb index is defined as $$ReZG_3(\Gamma)=\sum_{ab\in E(\Gamma)}\deg_\Gamma(a) ‎\deg_\Gamma(b)\Big(‎\deg_\Gamma(a)+‎\deg_\Gamma(b)\Big)‎‎,$$‎‎where $\deg_\Gamma(a)$ is the degree of‎ ‎vertex $a$‎. ‎We prove for any tree $T$ with $n$ vertices and maximum degree $\Delta$‎, ‎‎$ReZG_3(T)\geq‎16n+\Delta^3+2\Delta^2-13\Delta-26$ ‎when ‎‎$‎\Delta< n-1‎$ ‎and‎ $ReZG_3(T)=‎n\Delta^2+n\Delta-\Delta^2-\Delta$ ‎when ‎‎$‎\Delta=n-1‎$. ‎Also we determine the corresponding extremal trees‎. ‎‎
    Keywords: Zagreb ‎ Indices, ‎ Re-Defined Third Zagreb Index, ‎ ‎ Trees
  • Venkatesan Maitreyi, Suresh Elumalai *, Bala Selvraj Pages 547-561
    Let $d_x$ be the degree of the vertex $x$ in a graph $G$. The Randić index of $G$ is defined by $R(G) = \sum_{xy \in E(G)} (d_x d_y)^ {-\frac{1}{2}}$. Recently, Hasni et al. [Unicyclic graphs with Maximum Randi\'{c} indices, Communication in Combinatorics and Optimization, 1 (2023), 161--172] obtained the ninth to thirteenth maximum Randić indices among the unicyclic graphs with $n$ vertices. In this paper, we correct the ordering of Randić index of unicyclic graphs. In addition, we present the ordering of maximum Randi\'c index among bicyclic graphs of order $n$.
    Keywords: Unicyclic Graphs, Bicyclic Graphs, Randić Index
  • Muhammad Jamil, Shaban Anwer, Muhammad Azeem *, Ivan Gutman Pages 563-593
    Intuitionistic fuzzy graphs are generalizations of fuzzy graphs, in which each vertex is assigned an ordered pair whose first coordinate gives the membership value and the second coordinate gives the non-membership value. There are many theoretical parameters to study different types of graphs and fuzzy graphs, topological indices are one of them. Sombor indices are important in explaining the topology of a graph, and were found to possess useful applicative properties. The two versions of the Sombor indices ($SO_3$ and $SO_4$)are converted into an intuitionistic fuzzy framework, and then formulas for different kinds of graphs are calculated. Our study also involves setting up a network of vaccination centers during a pandemic and applying intuitionistic fuzzy-based topological indices to assess their performance. With the help of this application, we highlight the practical implication and benefits of employing intuitionistic fuzzy-based techniques in vaccination centers. Through a comparative analysis, we evaluate which index is more efficient.
    Keywords: Intuitionistic Fuzzy Graph, Vaccination Centers Based On Path, Cycle, Complete Graph, Sombor Indices
  • Lata Kamble *, Charusheela Deshpande, Bhagyashree Athawale Pages 595-599
    A graph $G$ with a vertex set $V$ and an edge set $E$ is called regular if the degree of every vertex is the same. A quasi-regular graph is a graph whose vertices have one of two degrees $r$ and $r-1$, for some positive integer $r$. A graph $G$ is said to be self-complementary if $G$ is isomorphic to it's complement $\overline{G}$. In this paper we give a new method for construction of regular and quasi-regular self-complementary graph.
    Keywords: Self-Complementary Graph, Regular Graph, Quasi-Regular Graph
  • Hamidreza Golmohammadi * Pages 601-615
    A total coalition in a graph $G=(V,E)$ consists of two disjoint sets of vertices $V_{1}$ and $V_{2}$, neither of which is a total dominating set but whose union $V_{1}\cup V_{2}$, is a total dominating set. A total coalition partition in a graph $G$ of order $n=|V|$ is a vertex partition $\tau = \{V_1, V_2, \dots , V_k \}$ such that every set $V_i \in \tau$ is not a total dominating set but forms a total coalition with another set $V_j\in \tau$ which is not a total dominating set. The total coalition number $TC(G)$ equals the maximum $k$ of a total coalition partition of $G$. In this paper, we determine the total coalition number of all cubic graphs of order $n \le 10$.
    Keywords: Coalition, Total Coalition, Cubic Graphs
  • Lutz Volkmann * Pages 617-625
    Let $G$ be a graph with vertex set $V(G)$. A double Roman dominating function (DRDF) on a graph $G$ is a function $f:V(G)\longrightarrow\{0,1,2,3\}$ having the property that if $f(v)=0$, then the vertex $v$ must have at least two neighbors assigned 2 under $f$ or one neighbor $w$ with $f(w)=3$, and if $f(v)=1$, then the vertex $v$ mus have at least one neighbor $u$ with $f(u)\ge 2$. If $f$ is a DRDF on $G$, then let $V_0=\{v\in V(G): f(v)=0\}$. A restrained double Roman dominating function is a DRDF $f$ having the property that the subgraph induced by $V_0$ does not have an isolated vertex. A set $\{f_1,f_2,\ldots,f_d\}$ of distinct restrained double Roman dominating functions on $G$ with the property that $\sum_{i=1}^df_i(v)\le 3$ for each $v\in V(G)$ is called a restrained double Roman dominating family (of functions) on $G$. The maximum number of functions in a restrained double Roman dominating family on $G$ is the restrained double Roman domatic number of $G$, denoted by $d_{rdR}(G)$. We initiate the study of the restrained double Roman domatic number, and we present different sharp bounds on $d_{rdR}(G)$. In addition, we determine this parameter for some classes of graphs.
    Keywords: Double Roman Domination, Restrained Double Roman Domination, Restrained Double Roman Domatic Number
  • Abdelhak Omar *, Ahmed Bouchou Pages 627-629
    In this short note, we report an erroneous result of Mojdeh, Parsian and Masoumi relating the double Roman domination number to the enclaveless number and the differential of a graph. ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎
    Keywords: Double Roman Domination Number, Trees, Differential
  • Bilal Rather, Hilal Ganie *, Mustapha Aouchiche Pages 631-656
    For a connected graph $G$ of order $n$, the distance Laplacian matrix $D^L(G)$ is defined as $D^L(G)=Tr(G)-D(G)$, where $Tr(G)$ is the diagonal matrix of vertex transmissions and $D(G)$ is the distance matrix of $G$. The largest eigenvalue of $D^L(G)$ is the distance Laplacian spectral radius of $G$ and the quantity $DLE(G)=\sum\limits_{i=1}^{n}|\rho^L_i(G)-\frac{2W(G)}{n}|$, where $W(G)$ is the Wiener index of $G$, is the distance Laplacian energy of $G$. Brooms of diameter $4$ are the trees obtained from the path $P_{5}$ by appending pendent vertices at some vertex of $ P_{5}$. One of the interesting and important problems in spectral graph theory is to find extremal graphs for a spectral graph invariant and ordering them according to this graph invariant. This problem has been considered for many families of graphs with respect to different graph matrices. In the present article, we consider this problem for brooms of diameter $4$ and their complements with respect to their distance Laplacian matrix. Formally, we discuss the distance Laplacian spectrum and the distance Laplacian energy of brooms of diameter $4$. We will prove that these families of trees can be ordered in terms of their distance Laplacian energy and the distance Laplacian spectral radius. Further, we obtain the distance Laplacian spectrum and the distance Laplacian energy of complement of the family of double brooms and order them in terms of the smallest non-zero distance Laplacian eigenvalue and the distance Laplacian energy.
    Keywords: Laplacian Matrix, Distance Laplacian Matrix, Distance Laplacian Energy, Broom Trees, Ordering
  • Abbas Kermanian, Farideh Heydari *, Mohammad Maghasedi Pages 657-663
    Let $(K_{n},H^-)$ be a complete sigraph of order $n$ whose negative edges induce a subgraph $H$. In this paper, we characterize $(K_n,H^-)$ with exactly 3 non-negative eigenvalues, where $H$ is a non-spanning two-cyclic subgraph of $K_n$.
    Keywords: Sigraph, Complete Graph, Two-Cyclic Graph, Non-Negative Eigenvalues
  • Kalika Prasad, Munesh Kumari, Hrishikesh Mahato * Pages 665-679
    In this paper, we propose a generalized Lucas matrix (a recursive matrix of higher order) obtained from the generalized Fibonacci sequences. We obtain their algebraic properties such as direct inverse calculation, recursive nature, etc. Then, we propose a modified public key cryptography using the generalized Lucas matrices as a key element that optimizes the keyspace construction complexity. Furthermore, we establish a key agreement for encryption-decryption with a combination of the terms of generalized Lucas sequences under the residue operation.
    Keywords: Affine-Hill Cipher, Cryptography, Fibonacci Sequence, Lucas Sequence, Lucas Matrix
  • Moussa Daamouch * Pages 681-693
    A digraph $D=(V,E)$ is $k$-transitive if for any directed $uv$-path of length $k$, we have $(u,v) \in E$. In this paper, we study the structure of strong $k$-transitive oriented graphs having large minimum in- or out-degree. We show that such oriented graphs are \emph{extended cycles}. As a consequence, we prove that Seymour's Second Neighborhood Conjecture (SSNC) holds for $k$-transitive oriented graphs for $k \leq 11$. Also we confirm Bermond--Thomassen Conjecture for $k$-transitive oriented graphs for $k \leq 11$. A characterization of $k$-transitive oriented graphs having a hamiltonian cycle for $k \leq 6$ is obtained immediately.
    Keywords: K-Transitive Digraph, Minimum Degree, Seymour’ S Second Neighborhood Conjecture, Bermond– Thomassen Conjecture, Hamiltonian Cycle
  • Pynshngain Dhar, John Jala Kharbhih * Pages 695-700
    In this paper, we will point out errors in Theorem 2, Theorem 4, Theorem 5, Proposition 2, Proposition 3, Theorem 8, and Theorem 9  by giving suitable counterexamples. The statements of Theorem 2, Theorem 5, Proposition 2 and Proposition 3 of this paper have been reformulated and proofs are given.
    Keywords: Graph Topology, Graph Topological Space, N-Closed, D-Closed
  • Angsuman Das, Manideepa Saha * Pages 701-715
    Let $G$ be a group and $S$ be the collection of all non-trivial proper subgroups of $G$. The co-maximal subgroup graph $\Gamma(G)$ of a group $G$ is defined to be a graph with $S$ as the set of vertices and two distinct vertices $H$ and $K$ are adjacent if and only if $HK=G$. In this paper, we study the comaximal subgroup graph on finite dihedral groups. In particular, we study order, maximum and minimum degree, diameter, girth, domination number, chromatic number and perfectness of comaximal subgroup graph of dihedral groups. Moreover, we prove some isomorphism results on comaximal subgroup graph of dihedral groups.
    Keywords: Dihedral Group, Graph Isomorphism, Perfect Graph