Search

The general first Zagreb index of a graph G , denoted by M 1 p (G) , is defined as the sum of powers d G p (u) over all vertices u of V (G) , where d G (u) denotes the degree of a vertex u in G. In this paper, we consider negative values of p and obtain sharp lower bounds on the general first Zagreb index of trees, unicyclic and bicyclic graphs in terms of their order and maximum vertex degrees. Also, the corresponding extremal graphs attaining the bounds are characterized. The results are then extended to other indices defined as sums over all vertices of contributions which are convex or concave functions of their degrees. [ABSTRACT FROM AUTHOR]

The concept of jump system, introduced by Bouchet and Cunningham (1995), is a set of integer points satisfying a certain exchange property. We consider the minimization of a separable convex function on a jump system. It is known that the problem can be solved by a greedy algorithm. In this paper, we are interested in whether the greedy algorithm has the geodesic property, which means that the trajectory of the solutions generated by the algorithm is a geodesic from the initial solution to a nearest optimal solution. We show that a special implementation of the greedy algorithm enjoys the geodesic property, while the original algorithm does not. As a corollary to this, we present a new greedy algorithm for linear optimization on a delta-matroid and show that the algorithm has the geodesic property. [ABSTRACT FROM AUTHOR]

For a graph G = (V G , E G) , a subset S ⊆ V G is called a maximum dissociation set if the induced subgraph G [ S ] does not contain P 3 as its subgraph, and the subset has maximum cardinality. The dissociation number of G is the number of vertices in a maximum dissociation set of G. This paper mainly studies the problem of determining the maximum values of the vertex-degree function index H f (G) = ∑ v ∈ V G f (d (v)) and characterizing the corresponding extremal graphs among all trees and unicyclic graphs with fixed order and dissociation number when f (x) is a strictly convex function. Firstly, we describe all the trees having the maximum vertex-degree function index H f (T) among trees with given order and dissociation number when f (x) is a strictly convex function. Then we determine the graphs having the maximum vertex-degree function index H f (T) among unicyclic graphs with given order and dissociation number when f (x) is a strictly convex function and satisfies f (5) + 2 f (3) + f (2) > 3 f (4) + f (1). [ABSTRACT FROM AUTHOR]

In Chirkov et al., (2019), classes of conic and discrete conic functions were introduced. In this paper we use the term convic instead conic. The class of convic functions properly includes the classes of convex functions, strictly quasiconvex functions and the class of quasiconvex polynomials. On the other hand, the class of convic functions is properly included in the class of quasiconvex functions. The discrete convic function is a discrete analogue of the convic function. In Chirkov et al., (2019), the lower bound 3 n − 1 log (2 ρ − 1) for the number of calls to the comparison oracle needed to find the minimum of the discrete convic function defined on integer points of some n -dimensional ball with radius ρ was obtained. But the problem of the existence of a polynomial (in log ρ for fixed n) algorithm for minimizing such functions has remained open. In this paper, we answer positively the question of the existence of such an algorithm. Namely, we propose an algorithm for minimizing discrete convic functions that uses 2 O (n 2 log n) log ρ calls to the comparison oracle and has 2 O (n 2 log n) poly (log ρ) bit complexity. [ABSTRACT FROM AUTHOR]

In this paper the problem of maximizing vertex-degree function index H f (G) for trees and unicyclic graphs G of order n and independence number s is solved for strictly convex functions f (x). In the case of unicyclic graphs f (x) must also satisfy strict inequality f (4) + 3 f (2) > 3 f (3) + f (1). These conditions are fulfilled by general first Zagreb index 0 R α (G) for α > 2 , second multiplicative Zagreb index ∏ 2 (G) and sum lordeg index S L (G). The extremal graphs are unique and they are stars or have diameter equal to three or to four. The same results are valid for the corresponding minimization problem when f (x) is strictly concave and the inequality is reversed. [ABSTRACT FROM AUTHOR]

In this paper we present efficient algorithms to compute the radius, diameter, incenter, circumcenter, width and k dimensional enclosing cylinder for convex polyhedral and convex polyhedral offset distance functions in plane and in ℜ d for several types of inputs. We get optimal algorithms when the time complexities are linear. Let the size of input (convex polyhedron P /set S of points/convex polyhedra) be n / N , respectively, size of distance function convex polygon/polyhedron Q be m and size of constraint convex polyhedral region R be r in plane or ℜ d. The radius, incenter and circumcenter of the convex polygon P in ℜ 2 can be optimally computed in linear time, i.e. O (n + m) and in time O (n + m + r) , if the incenter or circumcenter is additionally constrained in a convex polygon/polyhedron R. In ℜ d , the radius, incenter and circumcenter of a convex polyhedron as well as of a set of convex polyhedra, unconstrained or constrained, can be computed in O (N m) and O (N m + r) time respectively, for convex constraint polyhedral region R. We also compute the minimum stabbing sphere for a set of convex polyhedra, unconstrained or constrained, for the above mentioned distance functions in O (N m) -time or O (N m + r) -time respectively for convex constraint polyhedral region R in ℜ d. The diameter of a convex polygon in plane can be computed in O (n + m) time and the diameter of a convex polyhedron in ℜ d can be computed in O (n m) time. The width of a convex polyhedron can be computed in O (n + m) time and O (n 2 m) time, for ℜ 2 and ℜ d , respectively. The diameter and width of a set of convex polyhedra can be computed in O (N m) -time and (N 2 m) , respectively, in any dimensions. We also show how the k dimensional minimum enclosing/stabbing cylinder for the convex polyhedron P can be computed in O (n d − k + 2 m 2) in ℜ d and in O (n d m (n + m)) in ℜ d for k = 1. The k dimensional minimum enclosing/stabbing cylinder for the set of convex polyhedra S in ℜ d can be computed in O (N d − k + 2 m 2) -time. The diameter and width problems can also be solved for a set of points in ℜ d , either in time O (n m) or in time O (m T (n)) , where T (n) is the time complexity of the best convex hull computation algorithm for the given set of points. [ABSTRACT FROM AUTHOR]

A jump system is defined as a set of integer points (vectors) with a certain exchange property, generalizing the concepts of matroids, delta-matroids, and base polyhedra of integral polymatroids (or submodular systems). A discrete convexity concept is defined for functions on constant-parity jump systems and it has been used in graph theory and algebra. In this paper we call it "jump M-convexity" and extend it to "jump M ♮ -convexity" for functions defined on a larger class of jump systems. By definition, every jump M-convex function is a jump M ♮ -convex function, and we show the equivalence of these concepts by establishing an (injective) embedding of jump M ♮ -convex functions in n variables into the set of jump M-convex functions in n + 1 variables. Using this equivalence we show further that jump M ♮ -convex functions admit a number of natural operations such as aggregation, projection (partial minimization), convolution, composition, and transformation by a network. [ABSTRACT FROM AUTHOR]

The general sum-connectivity index of a graph G is χ α (G) = ∑ u v ∈ E (G) (d (u) + d (v)) α , where d (u) denotes the degree of vertex u ∈ V (G) , and α is a non-zero real number. Ali et al. (2019) proved that the unique graph obtained from the star S n by adding ν edge(s) between a fixed pendant vertex u and ν other pendant vertices, has the maximum χ α value in the collection of all n -vertex connected graphs having cyclomatic number ν with the constraints ν = 5 , n ≥ 7 , α > 1 or n ≥ 8 , 6 ≤ ν ≤ n − 2 , α ≥ 2 and conjectured that this result also holds for n ≥ 8 , 6 ≤ ν ≤ n − 2 and 1 < α < 2. In this paper, we provide a proof of this conjecture. [ABSTRACT FROM AUTHOR]

Abstract: In this paper we introduce an algorithm for the creation of polyhedral approximations for certain kinds of digital objects in a three-dimensional space. The objects are sets of voxels represented as strongly connected subsets of an abstract cell complex. The proposed algorithm generates the convex hull of a given object and modifies the hull afterwards by recursive repetitions of generating convex hulls of subsets of the given voxel set or subsets of the background voxels. The result of this method is a polyhedron which separates object voxels from background voxels. The objects processed by this algorithm and also the background voxel components inside the convex hull of the objects are restricted to have genus 0. The second aim of this paper is to present some practical improvements to the discussed convex hull algorithm to reduce computation time. [Copyright &y& Elsevier]

M-convex functions, which are a generalization of valuated matroids, play a central role in discrete convex analysis. Quadratic M-convex functions constitute a basic and important subclass of M-convex functions, which has a close relationship with phylogenetics as well as valued constraint satisfaction problems. In this paper, we consider the quadraticM-convexity testing problem (QMCTP), which is the problem of deciding whether a given quadratic function on { 0 , 1 } n is M-convex. We show that QMCTP is co-NP-complete in general, but is polynomial-time solvable under a natural assumption. Furthermore, we propose an O ( n 2 ) -time algorithm for solving QMCTP in the polynomial-time solvable case. [ABSTRACT FROM AUTHOR]

Recently, the concept of coarseness was introduced as a measure of how blended a 2-colored point set S is. In the definition of this measure, a convex partition Π , that is, a partition of S into sets { S 1 , … , S k } of S whose convex hulls are pairwise disjoint, is considered. The discrepancy of Π , denoted by d ( S , Π ) , is the smallest (bichromatic) discrepancy of the elements of Π . The coarseness of S , denoted by C ( S ) , is then defined as the maximum of d ( S , Π ) over all convex partitions Π of S . Roughly speaking, the value of the coarseness is high when we can split S into blocks, each with large discrepancy. It has been conjectured that computing the coarseness is NP-hard. In this paper, we study how to compute the coarseness for two constrained cases: (1) when the k elements of Π are separated by k − 1 pairwise parallel lines (strips) and, (2) the case in which the cardinality of the partition is fixed and the elements of Π are covered by pairwise disjoint axis-aligned rectangles (boxes). For the first case we present an O ( n 2 log 2 n ) -time algorithm, and show that such a computation problem is 3SUM-hard; for the second, we show that computing the coarseness with k boxes is NP-hard, when k is part of the input. For k fixed, we show that the coarseness can be computed in O ( n 2 k − 1 ) time and propose more efficient algorithms for k = 2 , 3 , 4 . [ABSTRACT FROM AUTHOR]

Abstract: Let be a pair consisting of a tree and a coloring of its vertices. We say that is a convex coloring if, for each color , the vertices in with color induce a subtree of . The convex recoloring problem (of trees) is defined as follows. Given a pair , find a recoloring of a minimum number of vertices of such that the resulting coloring is convex. This problem, known to be NP-hard, was motivated by problems on phylogenetic trees. We investigate here the convex recoloring problem on paths, denoted here as CRP. The main result concerns an approximation algorithm for a special case of CRP, denoted here as -CRP, restricted to paths in which the number of vertices of each color is at most , a problem known to be NP-hard. The best approximation result for CRP was obtained by Moran and Snir in 2007, who showed a -approximation algorithm. We show in this paper a -approximation algorithm for -CRP and show that its ratio analysis is tight. We also present an integer programming formulation for CRP and discuss some computational results obtained by exploring this formulation. [Copyright &y& Elsevier]

Abstract: This paper deals with the problem of extracting qualitative and quantitative information from few tomographic projections of an object without reconstructing this object. It focuses on the extraction of quantitative information, precisely the border perimeter estimation for a convex set from horizontal and vertical projections. In the case of a multiple reconstruction, lower and upper bounds for the perimeter are established. In the case of a unique reconstruction, we give conditions and a method for constructing an inscribed polygon in a convex set only from the convex-set projections. An inequality on border perimeter is proved when a convex set is included in another one. The convergence of the polygon perimeter, when the number of vertices increases, is established for such polygons. [Copyright &y& Elsevier]

Abstract: A set of vertices of a graph is a dominating set of if every vertex in has at least one neighbor in . A dominating set of is a paired-dominating set of if the induced subgraph, , has a perfect matching. The paired-domination problem is for a given graph and a positive integer to answer if has a paired-dominating set of size at most . The paired-domination problem is known to be NP-complete even for bipartite graphs. In this paper, we propose a linear time algorithm to compute a minimum paired-dominating set of a convex bipartite graph. [Copyright &y& Elsevier]

Abstract: For a graph , denote by its -iterated line graph and denote by its Wiener index. We prove that the function is convex in variable . Moreover, this function is strictly convex if is different from a path, a claw and a cycle. As an application we prove that for every if is a tree in which no leaf is adjacent to a vertex of degree 2, and . This is the first in a series of papers which resolve the question, whether there exists a tree for which for some , which was posed in [A.A. Dobrynin, R. Entringer, I. Gutman, Wiener index of trees: Theory and applications, Acta Appl. Math. 66 (2001), 211–249]. [Copyright &y& Elsevier]

Abstract: In the theory of two-sided matching markets there are two standard models: (i) the marriage model due to Gale and Shapley and (ii) the assignment model due to Shapley and Shubik. Recently, Eriksson and Karlander introduced a hybrid model, which was further generalized by Sotomayor. In this paper, we propose a common generalization of these models by utilizing the framework of discrete convex analysis introduced by Murota, and verify the existence of a pairwise-stable outcome in our general model. [Copyright &y& Elsevier]

M-convex functions, introduced by Murota (Adv. Math. 124 (1996) 272; Math. Prog. 83 (1998) 313), enjoy various desirable properties as “discrete convex functions.” In this paper, we propose two new polynomial-time scaling algorithms for the minimization of an M-convex function. Both algorithms apply a scaling technique to a greedy algorithm for M-convex function minimization, and run as fast as the previous minimization algorithms. We also specialize our scaling algorithms for the resource allocation problem which is a special case of M-convex function minimization. [Copyright &y& Elsevier]