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]

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]