On the stress transit function

Arun Anil, Manoj Changat, Tanja Dravec, Jeny Jacob, Lekshmi Kamal K.Sheela, Iztok Peterin, Polona Repolusk, Rishi Ranjan Singh · 2025

Read On the stress transit function by Arun Anil, Manoj Changat, Tanja Dravec, Jeny Jacob, Lekshmi Kamal K.Sheela, Iztok Peterin, Polona Repolusk, Rishi Ranjan Singh (2025) 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-2502-09153.txt.

Introduction

Anil and co-authors wrote a 2025 paper on a stress based way to slice up graphs. For two nodes, the stress interval gathers every node that lies on all shortest paths between them. A set of nodes is stress convex when it holds the full interval of any pair inside it.

The paper lays out basic traits of these intervals and marks the extreme nodes whose removal keeps the rest convex. Two counts come next: the least nodes whose intervals cover the graph, and the least nodes whose convex hull is the whole graph. The authors build graphs where the three counts drift far apart. For split graphs all three counts match. A closing proof shows that one of the counts is hard to compute, even for two sided graphs.

Catalog record

CREATORArun Anil, Manoj Changat, Tanja Dravec, Jeny Jacob, Lekshmi Kamal K.Sheela, Iztok Peterin, Polona Repolusk, Rishi Ranjan Singh
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE51 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-09153

Browse the full library · About the Tower of Babel

Full text

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

On the stress transit function Arun Anil, Manoj Changat, Tanja Dravec, Jeny Jacob, Lekshmi Kamal K.Sheela, Iztok Peterin, Polona Repolusk, Rishi Ranjan Singh Abstract The stress interval S ⁡ ( u , v ) S(u,v) between u , v ∈ V ⁡ ( G ) u,v\in V(G) is the set of all vertices in a graph G G that lie on every shortest u , v u,v -path. A set U ⊆ V ⁡ ( G ) U\subseteq V(G) is stress convex if S ⁡ ( u , v ) ⊆ U S(u,v)\subseteq U for any u , v ∈ U u,v\in U . A vertex v ∈ V ⁡ ( G ) v\in V(G) is s-extreme if V ⁡ ( G ) − v V(G)-v is a stress convex set in G G . The stress number s ​ n ​ ( G ) sn(G) of G G is the minimum cardinality of a set U U where ⋃ u , v ∈ U S ⁡ ( u , v ) = V ⁡ ( G ) \bigcup_{u,v\in U}S(u,v)=V(G) . The stress hull number s ​ h ​ ( G ) sh(G) of G G is the minimum cardinality of a set whose stress convex hull is V ⁡ ( G ) V(G) . In this paper, we present many basic properties of stress intervals. We characterize s-extreme vertices of a graph G G and construct graphs G G with arbitrarily large difference between the number of s-extreme vertices, s ​ h ​ ( G ) sh(G) and s ​ n ​ ( G ) sn(G) . Then we study these three invariants for some special graph families, such as graph products, split graphs, and block graphs. We show that in any split graph G G , s ​ h ​ ( G ) = s ​ n ​ ( G ) = | E ​ x ​ t s ​ ( G ) | sh(G)=sn(G)=|Ext_{s}(G)| , where E ​ x ​ t s ​ ( G ) Ext_{s}(G) is the set of s-extreme vertices of G G . Finally, we show that for k ∈ ℕ k\in\mathbb{N} , deciding whether s ​ n ​ ( G ) ≤ k sn(G)\leq k is NP-complete problem, even when restricted to bipartite graphs. Keywords: transit function, stress interval, stress convexity, stress number, stress hull number 1 Department of Futures Studies, University of Kerala, Thiruvananthapuram, India-695581. 2 University of Maribor, Faculty of Natural Sciences and Mathematics, Koroška 160, 2000 Maribor, Slovenia 3 Institute of Mathematics, Physics and Mechanics, Jadranska 19, 1000 Ljubljana, Slovenia 4 University of Maribor, Faculty of Electrical Engineering and Computer Science, Koroška 46, 2000 Maribor, Slovenia 5 Department of Computer Science & Engineering, Indian Institute of Technology, Bhilai, Chhattisgarh, India - 491002 6 MITS, Ernakulam, APJ Abdul Kalam Technological University, Kerala, India 1 Introduction and preliminaries A transit function on a nonempty finite set V is a function R:V\times V\rightarrow 2^{V} satisfying the three transit axioms for every x,y\in V : (t1) x\in R(x,y) ; (t2) R(x,y)=R(y,x) ; and (t3) R(x,x)=\{x\} . Prime examples of transit functions in graphs are the interval function I(u,v) defined on I:V(G)\times V(G)\longrightarrow 2^{V(G)} by I(u,v)=\{w\in V:w\text{ is on a shortest }u,v\text{-path}\}, (1) induced path function J(u,v) where we replace ‘shortest’ by ‘induced’ in ( 1 ) and all-paths function A(u,v) where we just delete ‘shortest’ in ( 1 ). The exhaustive monograph on the interval function was conducted by Mulder [ 27 ] , whereas the function J(u,v) was studied initially by Duchet [ 19 ] and Morgana and Mulder [ 25 ] , and A(u,v) by Sampathkumar [ 31 ] and Changat et al. [ 8 ] , all followed by many authors. However the first systematic study of I(u,v) from the transit functions perspective was presented later, also by Mulder [ 28 ] . The cut vertex transit function [ 11 , 33 ] (also on hypergraphs) and the longest path transit function [ 10 ] are other examples of interesting transit functions in graphs. Recently, a new transit function, named the toll function, and its axiomatic characterizations on AT-free graphs and interval graphs, was investigated in [ 1 , 24 ] . Convexity is a widely explored mathematical concept that incorporates various types of graph intervals and, consequently, transit functions for prime examples. A family \mathcal{C} of subsets of a finite set X is a convexity on X if \emptyset,X\in{\mathcal{C}} and \mathcal{C} is closed under intersections [ 37 ] . (If X is not finite, then also nested unions must belong to \mathcal{C} .) For a transit function R , convex (or R - convex ) sets are defined as sets S for which R(x,y)\subseteq S for any x,y\in S . In graph theory, the most investigated intervals are geodesic intervals that are built from I(u,v) and monophonic intervals arising from J(u,v) [ 9 ] . Betweenness centrality is a widely used measure to identify crucial vertices in graphs representing complex systems with flow [ 35 ] . It estimates the load or control of a vertex in a graph by computing the sum of the fraction of shortest paths passing through a given vertex [ 4 ] . Let s_{uv} be the number of distinct shortest paths between a vertex u and a vertex v . Let s_{uv}(i) be the number of distinct shortest paths between u and v that are passing through vertex i . The betweenness centrality of a vertex i is calculated as \sum_{|\{u,i,v\}|=3}\frac{s_{uv}(i)}{s_{uv}} , as defined by Freeman [ 20 ] . A similar yet simplified measure is the stress centrality [ 34 ] , which assumes that the importance of a vertex is proportional to the number of shortest paths passing through that vertex. Let u,v,x\in V . The stress of the vertex x depending on a pair of vertices u,v , is denoted as s_{uv}(x) . This score estimates the potential of a vertex, say x , to control the flow between a pair of vertices in a network. Clearly, s_{uv}(u)=s_{uv}(v) which is exactly the number of all distinct shortest paths between u and v . Further, s_{uv}(x)=s_{vu}(x) for every x\in V . Observe also that, 0<s_{uv}(x)\leq s_{uv}(u) for any x\in I(u,v) and s_{uv}(x)=0 for any x\notin I(u,v) . Motivated by these remarks, it is evident that the vertices with s_{uv}(x)=s_{uv}(u) are critical for every shortest path between vertex u and v . For such vertices, \frac{s_{uv}(x)}{s_{uv}}=1 , which means that the contribution of shortest paths between vertices u and v in the betweenness score of vertex x is 1. If communication is assumed to be occurring through the shortest paths in a communication system, vertices with s_{uv}(x)=s_{uv}(u) are essential for any communication between vertex u and v . We use this concept to define the stress transit function of a graph G=(V,E) . The stress interval S:V\times V\to 2^{V} is S(u,v)=\{x\in I(u,v):s_{uv}(x)=s_{uv}(u)\}. Hence x\in S(u,v) if and only if every shortest path between u and v passes through x . From the definition of S(u,v) , we can see that S(u,v)\subseteq I(u,v) . Moreover, the stress interval represents also a transit function for a connected graph as (t1), (t2) and (t3) are

Read the complete text