Azarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21289420241201Spectral determination of trees with large diameter and small spectral radius6076231463210.22049/cco.2023.28648.1651ENXing GaoSchool of Mathematics and Statistics, Shandong University of Technology, Zibo 255049, ChinaXuanshi JiaHaide School, Ocean University of China, Qingdao 266100, ChinaJianFeng WangSchool of Mathematics and Statistics, Shandong University of Technology, Zibo 255049, ChinaMaurizio BrunettiDepartment of Mathematics and Applications, University of Naples Federico II, Naples, Italy0000-0002-2742-1919Journal Article20230512Yuan, Shao and Liu proved that the H-shape tree $H'_n =P_{1,2;n-3}^{1,n-6}$ minimizes the spectral radius among all graphs with order $n\geqslant 9$ and diameter $n-4$. In this paper, we achieve the spectral characterization of all graphs in the set $\mathscr{H}' = \{ H'_n\}_{n\geqslant 8}$. More precisely we show that $H'_n$ is determined by its spectrum if and only if $n \neq 8, 9,12$, and detect all cospectral mates of $H'_8$, $H'_9$ and $H'_{12}$. Divisibility between characteristic polynomials of graphs turns out to be an important tool to reach our goals.https://comb-opt.azaruniv.ac.ir/article_14632_1609c9f80e2096670a0855727dbdaf1a.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21289420241201Monophonic eccentric domination in graphs6256331455910.22049/cco.2023.28156.1460ENTitus P.Department of Mathematics, University College of Engineering Nagercoil, Anna University,
Tirunelveli Region, Nagercoil - 629 004, IndiaAjitha FancyJ.Department of Mathematics, Scott Christian College (Autonomous), Nagercoil - 629 003, IndiaJournal Article20221214For any two vertices $u$ and $v$ in a connected graph $G,$ the monophonic distance $d_m(u,v)$ from $u$ to $v$ is defined as the length of a longest $u-v$ monophonic path in $G$. The monophonic eccentricity $e_m(v)$ of a vertex $v$ in $G$ is the maximum monophonic distance from $v$ to a vertex of $G$. A vertex $v$ in $G$ is a monophonic eccentric vertex of a vertex $u$ in $G$ if $e_m(u) = d_m(u,v)$. A set $S \subseteq V$ is a monophonic eccentric dominating $set$ if every vertex in $V-S$ has a monophonic eccentric vertex in $S$. The monophonic eccentric domination number $\gamma_{me}(G)$ is the cardinality of a minimum monophonic eccentric dominating set of $G$. We investigate some properties of monophonic eccentric dominating sets. Also, we determine the bounds of monophonic eccentric domination number and find the same for some standard graphs.https://comb-opt.azaruniv.ac.ir/article_14559_493595c2b79f1aec2d2f79278cb460f7.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21289420241201Zero forcing number for Cartesian product of some graphs6356461456110.22049/cco.2023.28177.1471ENZeinab MontazeriDepartment of Mathematics, Faculty of Mathematical Sciences, Alzahra University, Tehran, IranNasrin SoltankhahDepartment of Mathematics, Faculty of Mathematical Sciences, Alzahra University, Tehran, Iran0000-0003-0006-4680Journal Article20221222The zero forcing number of a graph $G$, denoted $Z(G)$, is a graph parameter which is based on a color change rule that describes how to color the vertices. Zero forcing is useful in several branches of science such as electrical engineering, computational complexity and quantum control. In this paper, we investigate the zero forcing number for Cartesian products of some graphs. The main contribution of this paper is to introduce a new presentation of the Cartesian product of two complete bipartite graphs and to obtain the zero forcing number of these graphs. We also introduce a purely graph theoretical method to prove $Z(K_n \Box K_m)=mn-m-n+2$.https://comb-opt.azaruniv.ac.ir/article_14561_0048ed001d56bd5d91ff1e827188fb27.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21289420241201On $\gamma$-free, $\gamma$-totally-free and $\gamma$-fixed sets in graphs6476541458310.22049/cco.2023.28525.1600ENGowri NDepartment of Mathematics, S. D. College, Alappuzha-690 104, IndiaDavid A KalarkopDepartment of Studies in Mathematics, University of Mysore, Manasagangothri, Mysuru-570 006,
India0000-0001-9182-7449Subramanian ArumugamAdjunct Professor, Department of Computer Science and Engineering, Ramco Institute of
Technology, Rajapalayam-626 117, Tamil Nadu, India0000-0002-4477-9453Journal Article20230403Let $G=(V,E)$ be a connected graph. A subset $S$ of $V$ is called a $\gamma$-free set if there exists a $\gamma$-set $D$ of $G$ such that $S \cap D= \emptyset$. If further the induced subgraph $H=G[V-S]$ is connected, then $S$ is called a $cc$-$\gamma$-free set of $G$. We use this concept to identify connected induced subgraphs $H$ of a given graph $G$ such that $\gamma(H) \leq \gamma(G)$. We also introduce the concept of $\gamma$-totally-free and $\gamma$-fixed sets and present several basic results on the corresponding parameters. https://comb-opt.azaruniv.ac.ir/article_14583_d152ed7251d1ec1d4bba0fdff8f9eb62.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21289420241201Algebraic-based primal interior-point algorithms for stochastic infinity norm optimization6556921458110.22049/cco.2023.28256.1492ENBaha AlzalgDepartment of Mathematics, The University of Jordan, Amman, Jordan 119420000-0002-1839-8083Karima TamsaoueteDepartment of Mathematics, The University of Jordan, Amman, Jordan 11942Department of Mathematics, M’Hamed Bougara University of Boumerd´es, Algeria 22038Journal Article20230122We study the two-stage stochastic infinity norm optimization problem with recourse based on a commutative algebra. First, we explore and develop the algebraic structure of the infinity norm cone, and utilize it to compute the derivatives of the barrier recourse functions. Then, we prove that the barrier recourse functions and the composite barrier functions for this optimization problem are self-concordant families with reference to barrier parameters. These findings are used to develop interior-point algorithms based on primal decomposition for this class of stochastic programming problems. Our complexity results for the short- and long-step algorithms show that the dominant complexity terms are linear in the rank of the underlying cone. Despite the asymmetry of the infinity norm cone, we also show that the obtained complexity results match (in terms of rank) the best known results in the literature for other well-studied stochastic symmetric cone programs. Finally, we demonstrate the efficiency of the proposed algorithm by presenting some numerical experiments on both stochastic uniform facility location problems and randomly-generated problems.https://comb-opt.azaruniv.ac.ir/article_14581_9bed2156c3d83453b1fef49f20ee0883.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21289420241201On graphs with integer sombor indices6937051458410.22049/cco.2023.28334.1510ENMarzie SepehrDepartment of Mathematics, Shahed University, Tehran, IranNader Jafari RadDepartment of Mathematics, Shahed University, Tehran, IranJournal Article20230218Sombor index of a graph $G$ is defined by $SO(G) = \sum_{uv \in E(G)} \sqrt{d^2_G(u)+d^2_G(v)}$, where $d_G(v)$ is the degree of the vertex $v$ of $G$. An $r$-degree graph is a graph whose degree sequence includes exactly $r$ distinctive numbers. In this article, we study $r$-degree connected graphs with integer Sombor index for $r \in \{5, 6, 7\}$. We show that: if $G$ is a 5-degree connected graph of order $n$ with integer Sombor index then $n \geq 50$ and the equality occurs if only if $G$ is a bipartite graph of size 420 with $SO(G) = 14830$; if $G$ is a 6-degree connected graph of order $n$ with integer Sombor index then $n \geq 75$ and the equality is established only for the bipartite graph of size $1080$; and if $G$ is a 7-degree connected graph of order $n$ with integer Sombor index then $n \geq 101$ and the equality is established only for the bipartite graph of size $1680$.https://comb-opt.azaruniv.ac.ir/article_14584_8d0ef76fd228409214f2430caf9898bf.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21289420241201Some properties and identities of hyperbolic generalized k-Horadam quaternions and octonions7077241460010.22049/cco.2023.28272.1495ENKalika PrasadDepartment of Mathematics, Central University of Jharkhand, 835205, India0000-0002-3653-5854Munesh KumariDepartment of Mathematics, Central University of Jharkhand, 835205, India0000-0002-6541-0284Can KızılateşDepartment of Mathematics, Zonguldak Bulent Ecevit University, 67100, Turkey0000-0002-7958-4226Journal Article20230127The aim of this paper is to introduce the hyperbolic generalized $k$-Horadam quaternions and octonions and investigate their algebraic properties. We present some properties and identities of these quaternions and octonions for generalized $k$-Horadam numbers. Moreover, we give some determinants related to the hyperbolic generalized $k$-Horadam quaternions and octonions. Finally, we evaluate its determinants through the Chebyshev polynomials of the second kind and give an illustrative example as well.https://comb-opt.azaruniv.ac.ir/article_14600_643259dd9c0b3a0146f483be26c1ef03.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21289420241201Cost, revenue and profit efficiency in multi-period network system: A DEA-R based approach7257461458710.22049/cco.2023.28179.1474ENMaghsood Ahmadkhanlou GharakhanloDepartment of Applied Mathematics, Islamic Azad University, Tabriz Branch, Tabriz, Iran0000000208688909Gasem TohidiDepartment of Mathematics, Islamic Azad University, Tehran Branch, Tehran, IranNima Azarmir ShotorbaniDepartment of Applied Mathematics, Islamic Azad University, Tabriz Branch, Tabriz, IranShabnam RazavyanDepartment of Mathematics, Islamic Azad University, South Tehran Branch, Tehran, IranRoohollah AbbasiDepartment of Management, Humanities College, Hazrat-e Masoumeh University, Qom, IranJournal Article20221227It has been proven that Data Envelopment Analysis is an efficient method to compare different decision making units with multiple inputs and outputs, but traditional Data Envelopment Analysis models suffers some difficulties: (a)- the inputs and outputs are not supposed to be given in terms of ratio. Thus, when the data are partially available, the decision maker will be unable to access missing data from the present data; (b) in measuring the efficiency of a set of decision making units for some periods, the conventional Data Envelopment Analysis based technique cannot handle the problem posed in a periodic form where the costs, profits and revenue efficiency of the main problems in the network structures are required. The contribution of this paper is four folded: (1) the cost, revenue and profit efficiency of each stages are calculated from the proposed method depends on the performance of the unit in both stages. (2) Our method evaluates the total cost, revenue and profit efficiency in a whole t(t=1,…,T) time periods derived from all periodic and every stage efficiency, (3) The proposed method in this study yields the efficiency measures deals with ratio data, (4) To elucidate the details of the proposed method, the proposed multi-period DEA-R method was employed to measure the efficiency of ten units in three separate time periods. Numerical examples are also provided to explain the presented methods.https://comb-opt.azaruniv.ac.ir/article_14587_016b44cbd8542fa47a99bf34e60994ca.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21289420241201Game chromatic number of honeycomb related networks7477571459110.22049/cco.2023.28663.1658ENMuhammad ImranDepartment of Mathematical Sciences,
United Arab Emirates University,
P.O. Box 15551, Al Ain,
United Arab Emirates0000-0002-2827-0462Syed Ahtsham Ul Haq BokharyCentre for Advanced Studies in Pure and Applied Mathematics, Bahauddin Zakariya University, Multan, Pakistan0000-0002-8957-0792Muhammad Shahzad AkhtarCentre for Advanced Studies in Pure and Applied Mathematics, Bahauddin Zakariya University, Multan, PakistanNaoki MatsumotoFaculty of Education, University of the Ryukyus, Okinawa, JapanJournal Article20230418Let $G$ be a simple connected graph having finite number of vertices (nodes). Let a coloring game is played on the nodes of $G$ by two players, Alice and Bob alternately assign colors to the nodes such that the adjacent nodes receive different colors with Alice taking first turn. Bob wins the game if he is succeeded to assign k distinct colors in the neighborhood of some vertex, where k is the available number of colors. Otherwise, Alice wins. The game chromatic number of G is the minimum number of colors that are needed for Alice to win this coloring game and is denoted by $\chi_{g}(G)$. In this paper, the game chromatic number $\chi_{g}(G)$ for some interconnecting networks such as infinite honeycomb network, elementary wall of infinite height and infinite octagonal network is determined. Also, the bounds for the game chromatic number $\chi_{g}(G)$ of infinite oxide network are explored.https://comb-opt.azaruniv.ac.ir/article_14591_62a5a58e43d38374984f6b0743006d77.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21289420241201Vector valued switching in the products of signed graphs7597711464710.22049/cco.2023.28758.1703ENAlbin MathewDepartment of Mathematics, Central University of Kerala, Kasaragod - 671316, Kerala, India0000-0002-2643-3416Germina K. ADepartment of Mathematics, Central University of Kerala, Kasaragod - 671316, Kerala, India0000-0002-2643-3416Journal Article20230616A signed graph is a graph whose edges are labeled either as positive or negative. The concepts of vector valued switching and balancing dimension of signed graphs were introduced by S. Hameed et al. In this paper, we deal with the balancing dimension of various products of signed graphs, namely the Cartesian product, the lexicographic product, the tensor product, and the strong product.https://comb-opt.azaruniv.ac.ir/article_14647_5d7cd3ce0dd7d5a12ba1fc8ae2cb7224.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21289420241201Strong domination number of some operations on a graph7737831460310.22049/cco.2023.28649.1652ENSaeid AlikhaniDepartment of Mathematical Sciences, Yazd University, 89195-741, Yazd, Iran0000-0002-1801-203XNima GhanbariDepartment of Informatics, University of Bergen, P.O. Box 7803, 5020 Bergen, NorwayHassan ZaherifarDepartment of Mathematical Sciences, Yazd University, 89195-741, Yazd, IranJournal Article20230512Let $G=(V(G),E(G))$ be a simple graph. A set $D\subseteq V(G)$ is a strong dominating set of $G$, if for every vertex $x\in V(G)\setminus D$ there is a vertex $y\in D$ with $xy\in E(G)$ and $\deg(x)\leq \deg(y)$. The strong domination number $\gamma_{st}(G)$ is defined as the minimum cardinality of a strong dominating set. In this paper, we examine the effects on $\gamma_{st}(G)$ when $G$ is modified by operations on edge (or edges) of $G$.https://comb-opt.azaruniv.ac.ir/article_14603_bf773c6132a8c6bd3daf4e4223ed1476.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21289420241201Bounds on sombor index and inverse sum indeg (ISI) index of graph operations7857981460910.22049/cco.2023.28718.1684ENFareeha JamalDepartment of Mathematical Sciences, College of Science, United Arab Emirate University
Al Ain 15551, Abu Dhabi, UAEMuhammad ImranDepartment of Mathematical Sciences, College of Science, United Arab Emirate University
Al Ain 15551, Abu Dhabi, UAE0000-0002-2827-0462Journal Article20230604Let $ G $ be a graph with vertex set $ V(G) $ and edge set $ E(G) $. Denote by $ d_G(u) $ the degree of a vertex $ u \in V(G) $. The Sombor index of $ G $ is defined as $ SO(G) = \sum_{uv \in E(G)} \sqrt{d_u^2 + d_v^2} $, whereas, the inverse sum indeg $ (ISI) $ index is defined as $ ISI(G) = \sum_{uv \in E(G)} \frac{d_{u}d_{v}}{d_{u} + d_{v}}. $ In this paper, we compute the bounds in terms of maximum degree, minimum degree, order and size of the original graphs $ G $ and $ H $ for Sombor and $ ISI $ indices of several graph operations like corona product, cartesian product, strong product, composition and join of graphs.https://comb-opt.azaruniv.ac.ir/article_14609_07c6a6da023d4f2fd3fed522a9b06c76.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21289420241201A note on the small quasi-kernels conjecture in digraphs7998031460810.22049/cco.2023.28155.1459ENMostafa BlidiaLAMDA-RO Laboratory, Department of Mathematics, University of Blida, B.P. 270, Blida, Algeria0000-0003-4662-6407Mustapha ChellaliLAMDA-RO Laboratory, Department of Mathematics, University of Blida, B.P. 270, Blida, Algeria0000-0001-5231-6195Journal Article20221214A subset $K$ of vertices of digraph $D=(V(D),A(D))$ is a kernel if the following two conditions are fulfilled: (i) no two vertices of $K$ are connected by an arc in any direction and (ii) every vertex not in $K$ has an ingoing arc from some vertex in $K.$ A quasi-kernel of $D$ is a subset $Q$ of vertices satisfying condition (i) and furthermore every vertex can be reached in at most two steps from $Q.$ A vertex is source-free if it has at least one ingoing arc. In 1976, P.L. Erdös and L.A. Székely conjectured that every source-free digraph $D$ has a quasi-kernel of size at most $\left\vert V(D)\right\vert /2.$ Recently, this conjecture has been shown to be true by Allan van Hulst for digraphs having kernels. In this note, we provide a short and simple proof of van Hulst's result. We additionally characterize all source-free digraphs $D$ having kernels with smallest quasi-kernels of size $\left\vert V(D)\right\vert /2.$https://comb-opt.azaruniv.ac.ir/article_14608_5b513a0043acd2a9b12a25a1c1def2cb.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21289420241201Characterization of product cordial dragon graphs8058111461010.22049/cco.2023.27882.1384ENMukti AcharyaDepartment of Mathematics, Christ University, Bangalore, India0000-0001-7910-5830Joseph Varghese KureetharaDepartment of Mathematics, Christ University, Bangalore, India0000-0001-5030-3948Journal Article20220614The vertices of a graph are to be labelled with 0 or 1 such that each edge gets the label as the product of its end vertices. If the number of vertices labelled with 0's and 1's differ by at most one and if the number of edges labelled with 0's and 1's differ by at most by one, then the labelling is called product cordial labelling. Complete characterizations of product cordial dragon graphs are given. We also characterize dragon graphs whose line graphs are product cordial.https://comb-opt.azaruniv.ac.ir/article_14610_8f0bd25d71ecd6d470e4d4bc008f946c.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21289420241201Some observations on sombor coindex of graphs8138251462110.22049/cco.2023.28762.1707ENEmina MilovanovićFaculty of Electronic Engineering, University of Niš, Niš, SerbiaStefan StankovFaculty of Electronic Engineering, University of Niš, Niš, SerbiaMarjan MatejićFaculty of Electronic Engineering, University of Niš, Niš, SerbiaIgor MilovanovićFaculty of Electronic Engineering, University of Niš, Niš, SerbiaJournal Article20230618Let $G=(V,E)$, $V=\left\{ v_{1},v_{2},\ldots ,v_{n}\right\}$, be a simple graph of order $n$ and size $m$, without isolated vertices. The Sombor coindex of a graph $G$ is defined as $\overline{SO}(G)=\sum_{i\nsim j}\sqrt{d_i^2+d_j^2}$ , where $d_i= d(v_i)$ is a degree of vertex $v_i$, $i=1,2,\ldots , n$. In this paper we investigate a relationship between Sombor coindex and a number of other topological coindices. https://comb-opt.azaruniv.ac.ir/article_14621_3c75938244a39803b488848b1e502cb5.pdf