Azarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21289220240601Independence Number and Connectivity of Maximal Connected Domination Vertex Critical Graphs1851961464810.22049/cco.2023.28629.1639ENNorahAlmalkiDepartment of Mathematics and Statistics, College of Science, Taif University, Saudi ArabiaPawatonKaemawichanuratDepartment of Mathematics, Faculty of Science, King Mongkut’s University of Technology, Thonburi, ThailandMathematics and Statistics with Applications (MaSA), Bangkok, ThailandJournal Article20230503A $k$-CEC graph is a graph $G$ which has connected domination number $\gamma_{c}(G) = k$ and $\gamma_{c}(G + uv) < k$ for every $uv \in E(\overline{G})$. A $k$-CVC graph $G$ is a $2$-connected graph with $\gamma_{c}(G) = k$ and $\gamma_{c}(G - v) < k$ for any $v \in V(G)$. A graph is said to be maximal $k$-CVC if it is both $k$-CEC and $k$-CVC. Let $\delta$, $\kappa$, and $\alpha$ be the minimum degree, connectivity, and independence number of $G$, respectively. In this work, we prove that for a maximal $3$-CVC graph, if $\alpha = \kappa$, then $\kappa = \delta$. We additionally consider the class of maximal $3$-CVC graphs with $\alpha < \kappa$ and $\kappa < \delta$, and prove that every $3$-connected maximal $3$-CVC graph when $\kappa < \delta$ is Hamiltonian connected.https://comb-opt.azaruniv.ac.ir/article_14648_7cd24310710b75753fe7ac54c88501b3.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21289220240601A Counterexample on the Conjecture and bounds on $\chi_{gd}$-number of Mycielskian of a graph1972041451210.22049/cco.2023.27950.1402ENDavidA KalarkopDepartment of Studies in Mathematics, University of Mysore,
Manasagangothri, Mysuru – 570 006, IndiaRRangarajanDepartment of Studies in Mathematics, University of Mysore,
Manasagangothri, Mysuru – 570 006, IndiaJournal Article20220803A coloring $C=(V_1, \dots, V_k)$ of $G$ partitions the vertex set $V(G)$ into independent sets $V_i$ which are said to be color classes with respect to the coloring $C$. A vertex $v$ is said to have a dominator (dom) color class in $C$ if there is color class $V_i$ such that $v$ is adjacent to all the vertices of $V_i$ and $v$ is said to have an anti-dominator (anti-dom) color class in $C$ if there is color class $V_j$ such that $v$ is not adjacent to any vertex of $V_j$. Dominator coloring of $G$ is a coloring $C$ of $G$ such that every vertex has a dom color class. The minimum number of colors required for a dominator coloring of $G$ is called the dominator chromatic number of $G$, denoted by $\chi_{d}(G)$. Global Dominator coloring of $G$ is a coloring $C$ of $G$ such that every vertex has a dom color class and an anti-dom color class. The minimum number of colors required for a global dominator coloring of $G$ is called the global dominator chromatic number of $G$, denoted by $\chi_{gd}(G)$. In this paper, we give a counterexample for the conjecture posed in [I. Sahul Hamid, M.Rajeswari, Global dominator coloring of graphs, Discuss. Math. Graph Theory 39 (2019), 325--339] that for a graph $G$, if $\chi_{gd}(G)=2\chi_{d}(G)$, then $G$ is a complete multipartite graph. We deduce upper and lower bound for the global dominator chromatic number of Mycielskian of the graph $G$ in terms of dominator chromatic number of $G$.https://comb-opt.azaruniv.ac.ir/article_14512_f27574bddf6e30e9de6ee7da1299dc64.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21289220240601Leech Graphs2052151445210.22049/cco.2022.27735.1339ENSeenaVargheseDepartment of Mathematics, Federal Institute of Science and Technology, Angamaly-683577, Ernakulam District, Kerala, IndiaAparna LakshmananSavithriDepartment of Mathematics, Cochin University of Science and Technology,Cochin-22, Kerala,IndiaS.ArumugamNational Centre for Advanced Research in Discrete Mathematics, Kalasalingam University
Anand Nagar, Krishnankoil-626 126, Tamil Nadu, IndiaJournal Article20220331Let $t_p(G)$ denote the number of paths in a graph $G$ and let $f:E\rightarrow \mathbb{Z}^+$ be an edge labeling of $G$. The weight of a path $P$ is the sum of the labels assigned to the edges of $P$. If the set of weights of the paths in $G$ is $\{1,2,3,\dots,t_p(G)\}$, then $f$ is called a Leech labeling of $G$ and a graph which admits a Leech labeling is called a Leech graph. In this paper, we prove that the complete bipartite graphs $K_{2,n}$ and $K_{3,n}$ are not Leech graphs and determine the maximum possible value that can be given to an edge in the Leech labeling of a cycle.https://comb-opt.azaruniv.ac.ir/article_14452_ce94194bfd3899e3f4e232d5f7967cf6.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21289220240601Algorithmic complexity of triple Roman dominating functions on graphs2172321450410.22049/cco.2023.27884.1385ENAbolfazlPoureidiFaculty of Mathematical Sciences, Shahrood University of Technology, Shahrood, IranJafarFathaliFaculty of Mathematical Sciences, Shahrood University of Technology, Shahrood, IranJournal Article20220615Given a graph $G=(V,E)$, a function $f:V\to \{0,1,2,3,4\}$ is a triple Roman dominating function (TRDF) of $G$, for each vertex $v\in V$, (i) if $f (v ) = 0 $, then $v$ must have either one neighbour in $V_4$, or either two neighbours in $V_2 \cup V_3$ (one neighbour in $V_3$) or either three neighbours in $V_2 $, (ii) if $f (v ) = 1 $, then $v$ must have either one neighbour in $V_3 \cup V_4$ or either two neighbours in $V_2 $, and if $f (v ) = 2 $, then $v$ must have one neighbour in $V_2 \cup V_3\cup V_4$. The triple Roman domination number of $G$ is the minimum weight of an TRDF $f$ of $G$, where the weight of $f$ is $\sum_{v\in V}f(v)$. The triple Roman domination problem is to compute the triple Roman domination number of a given graph. In this paper, we study the triple Roman domination problem. We show that the problem is NP-complete for the star convex bipartite and the comb convex bipartite graphs and is APX-complete for graphs of degree at~most~4. We propose a linear-time algorithm for computing the triple Roman domination number of proper interval graphs. We also give an $( 2 H(\Delta(G)+1) -1 )$-approximation algorithm for solving the problem for any graph $G$, where $ \Delta(G)$ is the maximum degree of $G$ and $H(d)$ denotes the first $d$ terms of the harmonic series. In addition, we prove that for any $\varepsilon>0$ there is no $(1/4-\varepsilon)\ln|V|$-approximation polynomial-time algorithm for solving the problem on bipartite and split graphs, unless NP $\subseteq$ DTIME $(|V|^{O(\log\log|V |)})$.https://comb-opt.azaruniv.ac.ir/article_14504_824ad2afbe9547b62e36277046b7a132.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21289220240601Total Chromatic Number for Certain Classes of Lexicographic Product Graphs2332401447810.22049/cco.2022.27736.1333ENT.P.SandhiyaDepartment of Mathematics, Amrita School of Physical Sciences - Coimbatore, Amrita Vishwa Vidyapeetham, IndiaJ.GeethaDepartment of Mathematics, Amrita School of Physical Sciences - Coimbatore, Amrita Vishwa Vidyapeetham, IndiaK.SomasundaramDepartment of Mathematics, Amrita School of Physical Sciences - Coimbatore, Amrita Vishwa Vidyapeetham, IndiaJournal Article20220328A total coloring of a graph $G$ is an assignment of colors to all the elements (vertices and edges) of the graph in such a way that no two adjacent or incident elements receive the same color. The total chromatic number of $G$, denoted by $\chi''(G)$, is the minimum number of colors which need for total coloring of $G$. The Total Coloring Conjecture (TCC) made independently by Behzad and Vizing which claims that, $\Delta(G)+1 \leq \chi''(G) \leq \Delta(G)+2 $, where $\Delta(G)$ is the maximum degree of $G$. The lower bound is sharp and the upper bound remains to be proved. In this paper, we prove the TCC for certain classes of lexicographic and deleted lexicographic products of graphs. Also, we obtained the lower bound for certain classes of these products.https://comb-opt.azaruniv.ac.ir/article_14478_6ae5822cff5fd512923619eaae0409a8.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21289220240601The crossing numbers of join product of four graphs on six vertices with discrete graphs2412521452710.22049/cco.2023.27911.1393ENMichalStašDepartment of Mathematics and Theoretical Informatics, Faculty of Electrical Engineering and
Informatics, Technical University, 042 00 Košice, Slovak RepublicJournal Article20220706The main aim of the paper is to give the crossing number of the join product $G^\ast + D_n$ for the graph $G^\ast$ isomorphic to 4-regular graph on six vertices except for two distinct edges with no common vertex such that two remaining vertices are still adjacent, and where $D_n$ consists of $n$ isolated vertices. The proofs are done with possibility of an existence of a separating cycle in some particular drawing of the investigated graph $G^\ast$ and also with the help of well-known exact values for crossing numbers of join products of two subgraphs $H_k$ of $G^\ast$ with discrete graphs.https://comb-opt.azaruniv.ac.ir/article_14527_ab90f3f711824ade768067b0ac9ba2fb.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21289220240601Balance theory: An extension to conjugate skew gain graphs2532621446610.22049/cco.2022.27933.1397ENShahul HameedKoombailDepartment of Mathematics, K M M Government Women’s College, Kannur - 670004, Kerala, IndiaRamakrishnanK ODepartment of Mathematics, K M M Government Women’s College, Kannur - 670004, Kerala, IndiaJournal Article20220723We extend the notion of balance from the realm of signed and gain graphs to conjugate skew gain graphs which are skew gain graphs where the labels on the oriented edges get conjugated when we reverse the orientation. We characterize the balance in a conjugate skew gain graph in several ways especially by dealing with its adjacency matrix and the $g$-Laplacian matrix. We also deal with the concept of anti-balance in conjugate skew gain graphs.https://comb-opt.azaruniv.ac.ir/article_14466_8929c6504b7a82b6b7a07c3e5da470f8.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21289220240601The Length of the Longest Sequence of Consecutive FS-double Squares in a Word2632771449210.22049/cco.2022.27917.1395ENMaithileePatawarDepartment of Computer Science & Engineering, Indian Institute of Technology Guwahati, IndiaKalpeshKapoorDepartment of Mathematics, Indian Institute of Technology Guwahati, IndiaJournal Article20220710A square is a concatenation of two identical words, and a word $w$ is said to have a square $yy$ if $w$ can be written as $xyyz$ for some words $x$ and $z$. It is known that the ratio of the number of distinct squares in a word to its length is less than two, and any location of a word could begin with two distinct squares which are appearing in the word for the last time. A square whose first location starts with the last occurrence of two distinct squares is an FS-double square. We explore and identify the conditions under which a sequence of locations in a word starts with FS-double squares. We first find the structure of a word that begins with two consecutive FS-double squares and obtain its properties that enable us to extend the sequence of FS-double squares. It is proved that the length of the longest sequence of consecutive FS-double squares in a word of length $n$ is at most $\frac{n}{7}$. We show that the squares in the longest sequence of consecutive FS-double squares are conjugates.https://comb-opt.azaruniv.ac.ir/article_14492_bb31e36752033a0097464ede10256904.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21289220240601Mathematical results on harmonic polynomials2792951466010.22049/cco.2023.28920.1779ENWalterCarballosaDepartment of Mathematics and Statistics, Florida International University, 11200 SW 8th Street,
Miami, FL 33199, USAJ. E.NápolesDepartamento de Matemáticas, Universidad Nacional de Nordeste, Avenida de la Libertad 5450,
3400 Corrientes, ArgentinaJosé M.RodríguezDepartamento de Matemáticas, Universidad Carlos III de Madrid, Avenida de la Universidad 30,
28911 Leganés, Madrid, SpainO.RosarioFacultad de Matemáticas, Universidad Autónoma de Guerrero, Carlos E. Adame No.54, Col.
Garita, 39650 Acalpulco Gro., MexicoJosé M.SigarretaFacultad de Matemáticas, Universidad Autónoma de Guerrero, Carlos E. Adame No.54, Col.
Garita, 39650 Acalpulco Gro., MexicoJournal Article20230812The harmonic polynomial was defined in order to understand better the harmonic topological index. Here, we obtain several properties of this polynomial, and we prove that several properties of a graph can be deduced from its harmonic polynomial. Also, we prove that graphs with the same harmonic polynomial share many properties although they are not necessarily isomorphic.https://comb-opt.azaruniv.ac.ir/article_14660_8071a376a70bf0cc79490badada350e3.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21289220240601Some algebraic properties of the subdivision graph of a graph2973071454010.22049/cco.2023.28270.1494ENSeyed MortezaMirafzalDepartment of Mathematics, Faculty of Basic Sciences, Lorestan University, Khorramabad, IranJournal Article20230126Let $G=(V,E)$ be a connected graph with the vertex-set $V$ and the edge-set $E$. The subdivision graph $S(G)$ of the graph $G$ is obtained from $G$ by adding a vertex in the middle of every edge of $G$. In this paper, we investigate some properties of the graphs $S(G)$ and $L(S(G))$, where $L(S(G))$ is the line graph of $S(G)$. We will see that $S(G)$ and $L(S(G))$ inherit some properties of $G$. For instance, we show that if $G \ncong C_n$, then $Aut(G) \cong Aut(L(S(G)))$ (as abstract groups), where $C_n$ is the cycle of order $n$.https://comb-opt.azaruniv.ac.ir/article_14540_8e3d003dc6520a376bae52f416898bd7.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21289220240601Triangular Tile Latching System3093161447010.22049/cco.2022.27994.1415ENK.Kanchan DeviNational Centre for Advanced Research in Discrete Mathematics (n-CARDMATH),
Kalasalingam Academy of Research and Education, Krishnankoil-626126, IndiaS.ArumugamNational Centre for Advanced Research in Discrete Mathematics (n-CARDMATH),
Kalasalingam Academy of Research and Education, Krishnankoil-626126, IndiaJournal Article20220910A triangular tile latching system consists of a set $\Sigma$ of equilateral triangular tiles with at least one latchable side and an attachment rule which permits two tiles to get latched along a latchable side. In this paper we determine the language generated by a triangular tile latching system in terms of planar graphs.https://comb-opt.azaruniv.ac.ir/article_14470_65580e61a0ee9e8bdfc16738cf91a029.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21289220240601Power Dominator Chromatic Numbers of Splitting Graphs of Certain Classes of Graphs3173271451310.22049/cco.2023.27744.1337ENK.Sathish KumarDepartment of Mathematics, Madras Christian College, Chennai 600 059, IndiaN.Gnanamalar DavidSchool of Mathematics, Computer Science and Engineering, Liverpool Hope University, Liverpool,
L16 9JD, UKAtulya K.NagarSchool of Mathematics, Computer Science and Engineering, Liverpool Hope University, Liverpool,
L16 9JD, UKSubramanianK GSchool of Mathematics, Computer Science and Engineering, Liverpool Hope University, Liverpool,
L16 9JD, UKJournal Article20220331Domination in graphs and coloring of graphs are two main areas of investigation in graph theory. Power domination is a variant of domination in graphs introduced in the study of the problem of monitoring an electric power system. Based on the notions of power domination and coloring of a graph, the concept of power dominator coloring of a graph was introduced. The minimum number of colors required for power dominator coloring of a graph $G$ is called the power dominator chromatic number $\chi_{pd}(G)$ of $G,$ which has been computed for some classes of graphs. Here we compute the power dominator chromatic number for splitting graphs of certain classes of graphs.https://comb-opt.azaruniv.ac.ir/article_14513_5f6352a9398748f3c71dcfb8770f5935.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21289220240601A new construction for µ-way Steiner trades3293381451910.22049/cco.2023.27862.1373ENSaeedehRashidiDepartment of Applied Mathematics, Faculty of Mathematics and Computer,
Shahid Bahonar University of Kerman, Kerman, IranNasrinSoltankhahDepartment of Mathematics, Faculty of mathematical Sciences, Alzahra University, Tehran, IranJournal Article20220604A $\mu$-way $(v,k,t)$ trade $T$ of volume $m$ consists of $\mu$ pairwise disjoint collections $T_1, \ldots ,T_{\mu}$, each of $m$ blocks of size $k$ such that for every $t$-subset of a $v$-set $V,$ the number of blocks containing this $t$-subset is the same in each $T_i$ for $1\leq i\leq \mu$. If any $t$-subset of the $v$-set $V$ occurs at most once in each $T_i$ for $1\leq i\leq \mu$, then $T$ is called a $\mu$-way $(v,k,t)$ Steiner trade. In 2016, it was proved that there exists a 3-way $(v,k,2)$ Steiner trade of volume $m$ when $12(k-1)\leq m$ for each $k$. Here we improve the lower bound to $8(k-1)$ for even $k$, by using a recursive construction.https://comb-opt.azaruniv.ac.ir/article_14519_c24c3eb342699a30b4a6a2afb232428f.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21289220240601Signed total Italian $k$-domination in digraphs3393511453110.22049/cco.2023.27872.1377ENLutzVolkmannLehrstuhl II für Mathematik, RWTH Aachen University, 52056 Aachen, GermanyJournal Article20220609Let $k\ge 1$ be an integer, and let $D$ be a finite and simple digraph with vertex set $V(D)$. A signed total Italian $k$-dominating function (STIkDF) on a digraph $D$ is a function $f:V(D)\rightarrow\{-1,1,2\}$ satisfying the conditions that (i) $\sum_{x\in N^-(v)}f(x)\ge k$ for each vertex $v\in V(D)$, where $N^-(v)$ consists of all vertices of $D$ from which arcs go into $v$, and (ii) each vertex $u$ with $f(u)=-1$ has an in-neighbor $v$ for which $f(v)=2$ or two in-neighbors $w$ and $z$ with $f(w)=f(z)=1$. The weight of an STIkDF $f$ is $\omega(f)=\sum_{v\in V(D)}f(v)$. The signed total Italian $k$-domination number $\gamma_{stI}^k(D)$ of $D$ is the minimum weight of an STIkDF on $D$. In this paper we initiate the study of the signed total Italian $k$-domination number of digraphs, and we present different bounds on $\gamma_{stI}^k(D)$. In addition, we determine the signed total Italian $k$-domination number of some classes of digraphs.https://comb-opt.azaruniv.ac.ir/article_14531_f1baab7c0a57df721eb7509b4c56f46e.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21289220240601A path-following algorithm for stochastic quadratically constrained convex quadratic programming in a Hilbert space3533871454310.22049/cco.2023.28129.1452ENAmira AchouakOulhaDepartment of Mathematics, The University of Jordan, Amman 11942, JordanBahaAlzalgDepartment of Mathematics, The University of Jordan, Amman 11942, JordanJournal Article20221130We propose logarithmic-barrier decomposition-based interior-point algorithms for solving two-stage stochastic quadratically constrained convex quadratic programming problems in a Hilbert space. We prove the polynomial complexity of the proposed algorithms, and show that this complexity is independent on the choice of the Hilbert space, and hence it coincides with the best-known complexity estimates in the finite-dimensional case. We also apply our results on a concrete example from the stochastic control theory.https://comb-opt.azaruniv.ac.ir/article_14543_eea2bf024a75af5d29ff9f1f1f30565e.pdf