Azarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21282220170901Primal-dual path-following algorithms for circular programming65851363110.22049/cco.2017.25865.1051ENBaha AlzalgThe University of Jordan0000-0002-1839-8083Mohammad PirhajiShahrekord UniversityJournal Article20170123Circular programming problems are a new class of convex optimization problems that include second-order cone programming problems as a special case. Alizadeh and Goldfarb [Math. Program. Ser. A 95 (2003) 3-51] introduced primal-dual path-following algorithms for solving second-order cone programming problems. In this paper, we generalize their work by using the machinery of Euclidean Jordan algebras associated with the circular cones to derive primal-dual path-following interior point algorithms for circular programming problems. We prove polynomial convergence of the proposed algorithms by showing that the circular logarithmic barrier is a strongly self-concordant barrier. The numerical examples show the path-following algorithms are simple and efficient.https://comb-opt.azaruniv.ac.ir/article_13631_3b92d66c63867691344b503a2f0746f7.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21282220170901Reformulated F-index of graph operations87981363010.22049/cco.2017.13630ENHamideh AramDepartment of Mathematics
Gareziaeddin Center, Khoy Branch, Islamic Azad University, Khoy, Iran0000-0003-3894-9214Nasrin DehgardiDepartment of Mathematics and Computer Science,
Sirjan University of Technology
Sirjan, I.R. Iran0000-0001-8214-6000Journal Article20170318The first general Zagreb index is defined as $M_1^\lambda(G)=\sum_{v\in V(G)}d_{G}(v)^\lambda$ where $\lambda\in \mathbb{R}-\{0,1\}$. The case $\lambda=3$, is called F-index. Similarly, reformulated first general Zagreb index is defined in terms of edge-drees as $EM_1^\lambda(G)=\sum_{e\in E(G)}d_{G}(e)^\lambda$ and the reformulated F-index is $RF(G)=\sum_{e\in E(G)}d_{G}(e)^3$. In this paper, we compute the reformulated F-index for some graph operations.https://comb-opt.azaruniv.ac.ir/article_13630_719b7afc30e723e9cbae02669009d3c6.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21282220170901On leap Zagreb indices of graphs991171364310.22049/cco.2017.25949.1059ENIvan GutmanUniversity of Kragujevac0000-0001-9681-1550Ahmed MNajiDepartment of Mathematics, University of Mysore, Mysusu, India0000-0003-0007-8927Nandappa DSonerDepartment of Mathematics, University of Mysore, Mysuru, IndiaJournal Article20170530The first and second Zagreb indices of a graph are equal, respectively, to the sum of squares of the vertex degrees, <br />and the sum of the products of the degrees of pairs of adjacent vertices. We now consider analogous graph invariants, based on the second degrees of vertices (number of their second neighbors), called leap Zagreb indices. A number of their basic properties is established.https://comb-opt.azaruniv.ac.ir/article_13643_fc88ed6fdf52b7f7a7ad4b621f695992.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21282220170901Some results on the complement of a new graph associated to a commutative ring1191381364410.22049/cco.2017.25908.1053ENS. VisweswaranSaurashtra UniversityAnirudhdha ParmarSaurashtra UniversityJournal Article20170307The rings considered in this article are commutative with identity which admit at least one nonzero proper ideal. Let $R$ be a ring. We denote the collection of all ideals of $R$ by $\mathbb{I}(R)$ and $\mathbb{I}(R)\backslash \{(0)\}$ by $\mathbb{I}(R)^{*}$. Alilou et al. [A. Alilou, J. Amjadi and S.M. Sheikholeslami, {\em A new graph associated to a commutative ring}, Discrete Math. Algorithm. Appl. {\bf 8} (2016) Article ID: 1650029 (13 pages)] introduced and investigated a new graph associated to $R$, denoted by $\Omega_{R}^{*}$ which is an undirected graph whose vertex set is $\mathbb{I}(R)^{*}\backslash \{R\}$ and distinct vertices $I, J$ are joined by an edge in this graph if and only if either $(Ann_{R}I)J = (0)$ or $(Ann_{R}J)I = (0)$. Several interesting theorems were proved on $\Omega_{R}^{*}$ in the aforementioned paper and they illustrate the interplay between the graph-theoretic properties of $\Omega_{R}^{*}$ and the ring-theoretic properties of $R$. The aim of this article is to investigate some properties of $(\Omega_{R}^{*})^{c}$, the complement of the new graph $\Omega_{R}^{*}$ associated to $R$.https://comb-opt.azaruniv.ac.ir/article_13644_1b27eaa14546119e0ee5915425b1cb0b.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21282220170901Approximation Solutions for Time-Varying Shortest Path Problem1391471364510.22049/cco.2017.25850.1047ENGholam Hassan ShirdelUniversity of Qom0000-0003-2759-4606Hassan RezapourUnuversity of QomJournal Article20170103Time-varying network optimization problem, which is NP-complete in the ordinary sense, are traditionally solved by specialized algorithms. This paper considers the time-varying shortest path problem, which can be optimally solved in $O\big(T(m+n)\big)$ time, where $T$ is a given integer. For this problem with arbitrary waiting times, we propose an approximate algorithm, which can find an acceptable solution of the problem with $O\big(\frac{T(m+n)}{k}\big)$ time complexity such that it evaluates only a subset of the values for $t \in \{0, 1,\ldots,T\}$.https://comb-opt.azaruniv.ac.ir/article_13645_0d39e0bfe8ae0a66991a25e4ac1ac564.pdfAzarbaijan Shahid Madani UniversityCommunications in Combinatorics and Optimization2538-21282220170901Graceful labelings of the generalized Petersen graphs1491591364610.22049/cco.2017.25918.1055ENAleksander VeselUniversity of MariborZehui ShaoSchool of Information Science & Technology, Chengdu University, Chengdu, China0000-0003-0764-4135Fei DengCollege of Information Science and Technology, Chengdu University of Technology, Chengdu, ChinaZepeng LiKey Laboratory of High Confidence Software Technologies, Peking University, Peking, ChinaJournal Article20170320A graceful labeling of a graph $G=(V,E)$ with $m$ edges is an injection $f: V(G) \rightarrow \{0,1,\ldots,m\}$ such that the resulting edge labels obtained by $|f(u)-f(v)|$ on every edge $uv$ are pairwise distinct. For natural numbers $n$ and $k$, where $n > 2k$, a generalized Petersen graph $P(n, k)$ is the graph whose vertex set is $\{u_1, u_2, \ldots, u_n\} \cup \{v_1, v_2, \ldots, v_n\}$ and its edge set is $\{u_iu_{i+1}, u_iv_i, v_iv_{i+k} : 1 \leq i \leq n \}$, where subscript arithmetic is done modulo $n$. We propose a backtracking algorithm with a specific static variable ordering and dynamic value ordering to find graceful labelings for generalized Petersen graphs. Experimental results show that the presented approach strongly outperforms the standard backtracking algorithm. The proposed algorithm is able to find graceful labelings for all generalized Petersen graphs $P(n, k)$ with $n \le 75$ within only several seconds. https://comb-opt.azaruniv.ac.ir/article_13646_07d33d001066dc9b0e695120e6125c8a.pdf