On Weighted Star–Convex Graphs

Angshuman R. Goswami · 2026

Read On Weighted Star–Convex Graphs by Angshuman R. Goswami (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-20900.txt.

Introduction

Goswami investigates geometric and sequential convexity inside graph theory, asking when a weighted graph counts as star-convex. He shows such a graph qualifies exactly when it holds a star-convex tree spanning all its leaves, with monotone paths joining each leaf to a shared center. Under mild assumptions, he also embeds a class of convex sequences into spider graphs so they become star-convex.

Catalog record

CREATORAngshuman R. Goswami
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE20813
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.20900

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On Weighted Star–Convex Graphs Thanks: The research of the author was supported by the “Ipar a Veszprémi Mérnökképzésért” Foundation Angshuman R. Goswami Abstract . The primary objective of this paper is to investigate the notions of geometric and sequential convexity within a graph-theoretic framework, with the aim of examining various structural properties and exploring the connection between these two branches of mathematics. A simple connected vertex-weighted graph G ⁡ ( V , E ) G(V,E) with a non-empty set of leaf vertices is said to be star-convex if there exists at least one node u ∈ V ⁡ ( G ) u\in V(G) such that, for every chosen leaf vertex v v , there is a monotone path (either increasing or decreasing) connecting v v to u u . One of the main results states that a graph G G is star-convex if and only if there exists a tree T ⊆ G T\subseteq G that contains all leaf vertices and is itself star-convex. On the other hand, a sequence ( u n ) n = 0 ∞ \big(u_{n}\big)_{n=0}^{\infty} is said to be convex if it satisfies the following inequality 2 ​ u i ≤ u i − 1 + u i + 1 for all i ∈ ℕ . \displaystyle 2u_{i}\leq u_{i-1}+u_{i+1}\qquad\mbox{for all}\quad i\in\mathbb{N}. We demonstrate that, under minimal assumptions, a class of convex sequences can be embedded into a spider graph so as to make it star-convex. The necessary definitions, background, motivation, and other relevant details are discussed in the following section. 2020 Mathematics Subject Classification Primary: 05C22,05C05; Secondary: 05C90, 39A12 Introduction Throughout this paper, \mathbb{R}_{+} denotes the set of non-negative real numbers. Let G(V,E) be a simple, connected, unweighted graph with vertex set V and edge set E . If a weight function w:V\to\mathbb{R}_{+} is assigned, then the resulting weighted graph is denoted by G(V,E,w) . It is important to note that the graphs G(V,E,w_{1}) and G(V,E,w_{2}) have the same vertex and edge sets but differ in their corresponding weight functions. Furthermore, V_{\ell}(\subseteq V) denotes the set of all vertices of G with degree exactly 1 . Similarly, a tree is denoted by T(V,E) , and the associated graph-theoretic terminology can be expressed using analogous notation. In convex geometry, a set X is said to be star-convex if there exists a point p\in X such that, for every x\in X , the unique line segment connecting p and x lies entirely within X . The subset consisting of all points having the same property as p is called the center of the set X . It is clear that every convex set is star-convex; however, the converse does not hold in general. A basic example of it is a connected compact star-shaped set. The study of star-convex bodies is important in optimization and related algorithmic questions. Further background in this direction can be found in [ 11 , 12 , 16 , 2 , 8 ] and the references therein. In graph theory, a tree T(V,E) having exactly one internal node v of degree at least 3 may be regarded as the graph-theoretic analogue of geometric or set-theoretic star-convexity. In the literature, this type of tree is usually referred to as a spider graph. In other words, a spider is a tree with exactly one vertex of degree greater than 2 , while all other internal vertices have degree exactly 2 . In a spider graph, the vertex of largest degree is called the hub , and each maximal path from the hub to a leaf is called a leg . Thus, a star is the special case in which every leg has length exactly 1 , so that a spider is a direct generalization of a star and a proper subclass of trees. If all legs of a spider have equal length, then the spider is called a balanced spider or regular spider . A number of structural and extremal results on spider graphs, including work related to the Erdős–Sós conjecture, may be found in [ 5 , 6 , 10 , 17 , 1 ] . On the other hand, for any non-empty and non-singleton convex set I\subseteq\mathbb{R} , a function f:I\to\mathbb{R} is said to be star-convex if there exists a point p\in I such that, for every x\in I , the line segment connecting (p,f(p)) and (x,f(x)) lies entirely either in the epigraph of f or in the hypograph of f . The notion of a star-convex function not only generalizes ordinary convexity but also highlights its relationship with star-convex sets. For further details, we refer to [ 14 , 9 , 8 ] . These interconnected concepts motivate us to analyse graphs that possess a spider-like structure by assigning weights to their vertices in a manner resembling a discrete convex or star-convex function. In other words, we aim to develop a graph-theoretic framework that mirrors the well-established features of star-convexity in function theory. We first introduce the notion of star-convex graphs and then discuss the concept of discrete convexity in order to build a bridge between these two settings. A weighted graph G(V,E,w) with non-empty V_{\ell} is said to be star-convex if there exists at least one vertex u\in V such that, for every v\in V_{\ell} , there exists a weighted-monotone path P connecting u and v_{\ell} . In other words, if P:=\{u,v_{1},\cdots,v_{\ell}\} , then one of the following holds: \displaystyle w(u)\leq w(u_{1})\leq\cdots\leq w(v_{\ell})\qquad\mbox{or}\qquad w(u)\geq w(u_{1})\geq\cdots\geq w(v_{\ell}). The collection of all such vertices u is called the core of the graph G , and we denote it by C(G) . Thus, the core consists of those vertices from which a weighted-monotone path can be traced to every vertex of degree 1 . Clearly, all the weighted graphs with exactly one leaf vertex turns to be star-convex. Hence in our research, we are interested to investigate only those star-convex graphs which contain atleast two leaf nodes. Besides, the motivation for studying weighted star-convexity is even more natural. For example, regardless of how weights are assigned to the vertices of a star graph, the resulting weighted graph is always star-convex. We therefore investigate several structural properties of weighted graphs possessing star-convexity. In particular, we show that both the union and the intersection of two graphs G_{1} and G_{2} can be star-convex provided that their cores have a non-empty intersection. We study star-convexity on trees and show that the extremal weights are attained either at leaf vertices or at vertices from the core. As one of our main results, we prove that a weighted graph G(V,E,w) is star-convex if and only if there exists a star-convex tree T(V_{\ell},E,w) extractable from G . One of the key objectives of this paper is to relate two distinct objects from different branches of discrete mathematics, convex sequences and spider graphs. A real-valued sequence \big(u_{n}\big)_{n=0}^{\infty} is called convex if the following discrete functional inequality is satisfied \displaystyle u_{i+1}-u_{i}\leq u_{j+1}-u_{j}\qquad\mbox{for all $i,j\in\mathbb{N}$}\quad\mbox{with}\quad i\leq j. The study of sequential convexity is important because every convex sequence can be viewed as a discrete analogue of a convex function, which makes it relevant in several discrete optimization problems. Moreover, many well-known sequences, such as arithmetic, geometric, partition-related, and Fibonacci-type sequences, may be studied within

Read the complete text