Azarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21287120220601Þ-energy of generalized Petersen graphs1161416810.22049/cco.2021.27102.1197ENPrajakta BharatJoshiResearch scholar, Department of mathematics, CHRIST (Deemed to be University), Bangalore, India0000-0003-2065-1663MayammaJosephDepartment of mathematics, Faculty, CHRIST (Deemed to be University), Bangalore.0000-0001-5819-247XJournal Article20210129For a given graph $ G $, its $mathscr{P}$-energy is the sum of the absolute values of the eigenvalues of the $mathscr{P}$-matrix of $ G $. In this article, we explore the $mathscr{P}$-energy of generalized Petersen graphs $ G(p,k) $ for various vertex partitions such as independent, domatic, total domatic and $ k $-ply domatic partitions and partition containing a perfect matching in $ G(p,k) $. Further, we present a python program to obtain the $mathscr{P}$-energy of $ G(p,k) $ for the vertex partitions under consideration and examine the relation between them.http://comb-opt.azaruniv.ac.ir/article_14168_650b69137e573da2101f8309df73ca34.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21287120220601Weak signed Roman k-domatic number of a graph17271416910.22049/cco.2021.26998.1178ENLutzVolkmannRWTH Aachen University0000-0003-3496-277XJournal Article20201112Let $kge 1$ be an integer. A { weak signed Roman $k$-dominating function} on a graph $G$ is<br />a function $f:V (G)longrightarrow {-1, 1, 2}$ such that $sum_{uin N[v]}f(u)ge k$ for every<br />$vin V(G)$, where $N[v]$ is the closed neighborhood of $v$.<br />A set ${f_1,f_2,ldots,f_d}$ of distinct weak signed Roman $k$-dominating<br />functions on $G$ with the property that $sum_{i=1}^df_i(v)le k$ for each $vin V(G)$, is called a<br />{ weak signed Roman $k$-dominating family} (of functions) on $G$. The maximum number of functions<br />in a weak signed Roman $k$-dominating family on $G$ is the { weak signed Roman $k$-domatic number} of $G$,<br />denoted by $d_{wsR}^k(G)$. In this paper we initiate the study of the weak signed Roman $k$-domatic number<br />in graphs, and we present sharp bounds for $d_{wsR}^k(G)$. In addition, we determine the weak signed Roman<br />$k$-domatic number of some graphs.http://comb-opt.azaruniv.ac.ir/article_14169_1e588e4245ba97d8d37a13423c97b545.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21287120220601A second-order corrector wide neighborhood infeasible interior-point method for linear optimization based on a specific kernel function29441417310.22049/cco.2021.27044.1185ENBehrouzKheirfamMathematicsorcid.org/0000-0001-7928-2618AfsanehNasrollahDepartment of Mathematics, Azarbaijan Shahid Madani UniversityJournal Article20201210In this paper, we present a second-order corrector infeasible<br />interior-point method for linear optimization in a large<br />neighborhood of the central path. The innovation of our method is to<br />calculate the predictor directions using a specific kernel function<br />instead of the logarithmic barrier function. We decompose the<br />predictor direction induced by the kernel function to two orthogonal<br />directions of the corresponding to the negative and positive<br />component of the right-hand side vector of the centering equation.<br />The method then considers the new point as a linear combination of<br />these directions along with a second-order corrector direction. The<br />convergence analysis of the proposed method is investigated and it<br />is proved that the complexity bound is<br />$mathcal{O}(n^{frac{5}{4}}logvarepsilon^{-1})$.http://comb-opt.azaruniv.ac.ir/article_14173_be36f496696d9c17ddbe54d1b26b21db.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21287120220601On the powers of signed graphs45511417410.22049/cco.2021.27083.1193ENShijinT VDepartment of Mathematics, Research Scholar, Central University of Kerala, Kasaragod, India.0000-0002-9850-4674GerminaK ADepartment of Mathematics, Associate Professor, Central University of Kerala, Kasaragod, IndiaShahul HameedKDepartment of Mathematics, Associate Professor, K M M Government Women's College, Kannur, India.Journal Article20210110A signed graph is an ordered pair $Sigma=(G,sigma),$ where $G=(V,E)$ is the underlying graph of $Sigma$ with a signature function $sigma:Erightarrow {1,-1}$.<br />In this article, we define the $n^{th}$ power of a signed graph and discuss some properties of these powers of signed graphs. As we can define two types of signed graphs as the power of a signed graph, necessary and sufficient conditions are given for an $n^{th}$ power of a signed graph to be unique. Also, we characterize balanced power signed graphs.http://comb-opt.azaruniv.ac.ir/article_14174_8602679ede9109adf00cd5022f7e70b4.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21287120220601Two upper bounds on the A_α-spectral radius of a connected graph53571417810.22049/cco.2021.27061.1187ENShariefuddinPirzadaDepartment of Mathematics, HazratbalJournal Article20201225If $A(G)$ and $D(G)$ are respectively the adjacency matrix and the diagonal matrix of vertex degrees of a connected graph $G$, the generalized adjacency matrix $A_{alpha}(G)$ is defined as $A_{alpha}(G)=alpha ~D(G)+(1-alpha)~A(G)$, where $0leq alpha leq 1$. The $A_{alpha}$ (or generalized) spectral radius $lambda(A_{alpha}(G))$ (or simply $lambda_{alpha}$) is the largest eigenvalue of $A_{alpha}(G)$. In this paper, we show that
$$ lambda_{alpha}leq alpha~Delta +(1-alpha)sqrt{2mleft(1-frac{1}{omega}right)}, $$<br />where $m$, $Delta$ and $omega=omega(G)$ are respectively the size, the largest degree and the clique number of $G$. Further, if $G$ has order $n$, then we show that
begin{equation*}<br /> lambda_{alpha}leq frac{1}{2}maxlimits_{1leq ileq n} left[alpha d_{i}+sqrt{ alpha^{2}d_{i}^{2}+4m_{i}(1-alpha)[alpha+(1-alpha)m_{j}] }right],<br />end{equation*}<br />where $d_{i}$ and $m_{i}$ are respectively the degree and the average 2-degree of the vertex $v_{i}$.http://comb-opt.azaruniv.ac.ir/article_14178_9ff8635c0123896b88601cc9982321d9.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21287120220601Total outer-convex domination number of graphs59681418010.22049/cco.2021.27141.1203ENRubelynYangyangUniversity of San Jose-Recoletos0000-0002-9585-429XMarylinTarongoyUniversity of San Jose-Recoletos0000-0002-7730-6206EvangelynRevillaUniversity of San Jose-Recoletos0000-0003-3330-0328Rona MaeBanlasanUniversity of San Jose-Recoletos0000-0003-3857-9831Jonecis ADayapUniversity of San Jose-Recoletos0000-0003-1047-1490Journal Article20210217In this paper, we initiate the study of total outer-convex domination as a new variant of graph domination and we show the close relationship that exists between this novel parameter and other domination parameters of a graph such as total domination, convex domination, and outer-convex domination. Furthermore, we obtain general bounds of total outer-convex domination number and, for some particular families of graphs, we obtain closed formulas.http://comb-opt.azaruniv.ac.ir/article_14180_0865ea14718c03117813a9b8e9a14985.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21287120220601The Tutte polynomial of matroids constructed by a family of splitting operations69791417910.22049/cco.2021.26995.1177ENMortezaKazemzadeUrmia UniversityHabibAzanchilerUrmia UniversityVahidGhorbaniUrmia University0000-0002-7301-6973Journal Article20201103To extract some more information from the constructions of matroids that arise from new operations, computing the Tutte polynomial, plays an important role. In this paper, we consider applying three operations of splitting, element splitting and splitting off to a binary matroid and then introduce the Tutte polynomial of resulting matroids by these operations in terms of that of original matroids.http://comb-opt.azaruniv.ac.ir/article_14179_eb9894472e6632c9215d72f4ac9f6992.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21287120220601New bounds on the energy of a graph81901421810.22049/cco.2021.26999.1179ENHajarShooshtaryDepartment of Mathematics
Esfahan University of TechnologyJonnathanRodriguezUniversidad de Antofagastahttps://orcid.org/00Journal Article20201114The energy of a graph G, denoted by <em>Ε(G)</em>, is defined as the sum of the absolute values of all eigenvalues of G. In this paper, lower and upper bounds for energy in some of the graphs are established, in terms of graph invariants such as the number of vertices, the number of edges, and the number of closed walks.http://comb-opt.azaruniv.ac.ir/article_14218_c0d0fb33f62d95fd6f0d313e62fb6f53.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21287120220601A counterexample to a conjecture of Jafari Rad and Volkmann91921421910.22049/cco.2021.27226.1214ENMostafaBlidiaDepartment of Mathematics, University of Blida 1.
B.P. 270, Blida, AlgeriaMustaphaChellaliDepartment of Mathematics, University of Blida 1.
B.P. 270, Blida, AlgeriaJournal Article20210422In this short note, we disprove the conjecture of Jafari Rad and Volkmann<br />that every $gamma $-vertex critical graph is $gamma _{R}$-vertex critical,<br />where $gamma (G)$ and $gamma _{R}(G)$ stand for the domination number and<br />the Roman domination number of a graph $G$, respectively.http://comb-opt.azaruniv.ac.ir/article_14219_d105f0d530108e7b8c566d7db0a2b731.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21287120220601Algorithmic Aspects of Quasi-Total Roman Domination in Graphs931041422010.22049/cco.2021.27126.1200ENVenkata Subba ReddyPNational Institute of Technology WarangalMangalVikasDepartment of Computer Science and Engineering, National Institute of Technology Warangal, India.Journal Article20210208For a simple, undirected, connected graph $G$($V,E$), a function $f : V(G) rightarrow lbrace 0, 1, 2 rbrace$ which satisfies the following conditions is called a quasi-total Roman dominating function (QTRDF) of $G$ with weight $f(V(G))=sum_{v in V(G)} f(v)$.<br /> C1). Every vertex $u in V(G)$ for which $f(u) = 0$ must be adjacent to at least one vertex $v$ with $f(v) = 2$, and <br /> C2). Every vertex $u in V(G)$ for which $f(u) = 2$ must be adjacent to at least one vertex $v$ with $f(v) geq 1$. <br /> For a graph $G$, the smallest possible weight of a QTRDF of $G$ denoted $gamma_{qtR}(G)$ is known as the textit{quasi-total Roman domination number} of $G$.<br /> The problem of determining $gamma_{qtR}(G)$ of a graph $G$ is called minimum quasi-total Roman domination problem (MQTRDP).<br /> In this paper, we show that the problem of determining whether $G$ has a QTRDF of weight at most $l$ is NP-complete for split graphs, star convex bipartite graphs, comb convex bipartite graphs and planar graphs.<br /> On the positive side, we show that MQTRDP for threshold graphs, chain graphs and bounded treewidth graphs is linear time solvable. Finally, an integer linear programming formulation for MQTRDP is presented.<br /> <br /> http://comb-opt.azaruniv.ac.ir/article_14220_e1aeb63f7a60db0a40f1bdb4295ae39a.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21287120220601On the 2-independence subdivision number of graphs1051121422410.22049/cco.2021.27060.1186ENNacéraMeddahDepartment of Mathematics
University of Blida
B.P. 270, Blida, AlgeriaMostafaBlidiaDepartment of Mathematics, University of Blida 1.
B.P. 270, Blida, AlgeriaMustaphaChellaliDepartment of Mathematics
University of Blida 1, B.P. 270, Blida, AlgeriaJournal Article20201224A subset $S$ of vertices in a graph $G=(V,E)$ is $2$-independent if every<br />vertex of $S$ has at most one neighbor in $S.$ The $2$-independence number<br />is the maximum cardinality of a $2$-independent set of $G.$ In this paper,<br />we initiate the study of the $2$-independence subdivision number $mathrm{sd}%<br />_{beta _{2}}(G)$ defined as the minimum number of edges that must be<br />subdivided (each edge in $G$ can be subdivided at most once) in order to<br />increase the $2$-independence number. We first show that for every connected<br />graph $G$ of order at least three, $1leq mathrm{sd}_{beta _{2}}(G)leq 2,$<br />and we give a necessary and sufficient condition for graphs $G$ attaining<br />each bound. Moreover, restricted to the class of trees, we provide a<br />constructive characterization of all trees $T$ with $mathrm{sd}_{beta<br />_{2}}(T)=2,$ and we show that such a characterization suggests an algorithm<br />that determines whether a tree $T$ hastextrm{ }$mathrm{sd}_{beta<br />_{2}}(T)=2$ or $mathrm{sd}_{beta _{2}}(T)=1$ in polynomial time.http://comb-opt.azaruniv.ac.ir/article_14224_e81b235babb9101de9451e1938646d95.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21287120220601A note on δ^(k)-colouring of the Cartesian product of some graphs1131201422510.22049/cco.2021.27114.1211ENSudevNaduvathChrist University, Bangalore, India.0000-0001-9692-4053Merlin ThomasEllumkalayilDepartment of Mathematics, Christ University, Bangalore, India.Journal Article20210323The chromatic number, $chi(G)$ of a graph $G$ is the minimum number of colours used in a proper colouring of $G$. In an improper colouring, an edge $uv$ is bad if the colours assigned to the end vertices of the edge is the same. Now, if the available colours are less than that of the chromatic number of graph $G$, then colouring the graph with the available colours lead to bad edges in $G$. The number of bad edges resulting from a $delta^{(k)}$-colouring of $G$ is denoted by $b_{k}(G)$. In this paper, we use the concept of $delta^{(k)}$-colouring and determine the number of bad edges in Cartesian product of some graphs.http://comb-opt.azaruniv.ac.ir/article_14225_7671b9be902fe5288eaea7c2a4aa2762.pdf