On the Stress Transit Function

Abstract The stress interval S ( u , v ) between $$u,v\in V(G)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>u</mml:mi> <mml:mo>,</mml:mo> <mml:mi>v</mml:mi> <mml:mo>∈</mml:mo> <mml:mi>V</mml:mi> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> is the set of all vertices in a graph G that lie on every shortest u , v -path. A set $$U \subseteq V(G)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>U</mml:mi> <mml:mo>⊆</mml:mo> <mml:mi>V</mml:mi> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> is stress convex if $$S(u,v) \subseteq U$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>S</mml:mi> <mml:mo>(</mml:mo> <mml:mi>u</mml:mi> <mml:mo>,</mml:mo> <mml:mi>v</mml:mi> <mml:mo>)</mml:mo> <mml:mo>⊆</mml:mo> <mml:mi>U</mml:mi> </mml:mrow> </mml:math> for any $$u,v\in U$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>u</mml:mi> <mml:mo>,</mml:mo> <mml:mi>v</mml:mi> <mml:mo>∈</mml:mo> <mml:mi>U</mml:mi> </mml:mrow> </mml:math> . A vertex $$v \in V(G)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>v</mml:mi> <mml:mo>∈</mml:mo> <mml:mi>V</mml:mi> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> is s-extreme if $$V(G)-\{v\}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>V</mml:mi> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> <mml:mo>-</mml:mo> <mml:mo>{</mml:mo> <mml:mi>v</mml:mi> <mml:mo>}</mml:mo> </mml:mrow> </mml:math> is a stress convex set in G . The stress number sn ( G ) of G is the minimum cardinality of a set U where $$\bigcup _{u,v \in U}S(u,v)=V(G)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mo>⋃</mml:mo> <mml:mrow> <mml:mi>u</mml:mi> <mml:mo>,</mml:mo> <mml:mi>v</mml:mi> <mml:mo>∈</mml:mo> <mml:mi>U</mml:mi> </mml:mrow> </mml:msub> <mml:mi>S</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>u</mml:mi> <mml:mo>,</mml:mo> <mml:mi>v</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>=</mml:mo> <mml:mi>V</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> . The stress hull number sh ( G ) of G is the minimum cardinality of a set whose stress convex hull is V ( G ). In this paper, we present many basic properties of stress intervals. We characterize s-extreme vertices of a graph G and construct graphs G with arbitrarily large difference between the number of s-extreme vertices, sh ( G ) and 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 , $$sh(G)=sn(G)=|\textrm{Ext}_s(G)|$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mrow> <mml:mi>s</mml:mi> <mml:mi>h</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>=</mml:mo> <mml:mi>s</mml:mi> <mml:mi>n</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>=</mml:mo> <mml:mo>|</mml:mo> </mml:mrow> <mml:msub> <mml:mtext>Ext</mml:mtext>