.png){kind=icon}
.png){kind=icon}
Return
On the Stress Transit Function
.png){kind=icon}
OA
AI
DOI：10.1007/s41980-025-01017-8.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
The stress interval S(u, v) between u,v is an element of V(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$u,v\in V(G)$$\end{document} is the set of all vertices in a graph G that lie on every shortest u, v-path. A set U subset of V(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$U \subseteq V(G)$$\end{document} is stress convex if S(u,v)subset of U\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$S(u,v) \subseteq U$$\end{document} for any u,v is an element of U\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$u,v\in U$$\end{document}. A vertex v is an element of V(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$v \in V(G)$$\end{document} is s-extreme if V(G)-{v}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$V(G)-\{v\}$$\end{document} is a stress convex set in G. The stress number sn(G) of G is the minimum cardinality of a set U where & xcup;u,v is an element of US(u,v)=V(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\bigcup _{u,v \in U}S(u,v)=V(G)$$\end{document}. 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)=|Exts(G)|\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$sh(G)=sn(G)=|\textrm{Ext}_s(G)|$$\end{document}, where Exts(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\textrm{Ext}_s(G)$$\end{document} is the set of s-extreme vertices of G. Finally, we show that for k is an element of N\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k \in \mathbb {N}$$\end{document}, deciding whether sn(G)<= k\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$sn(G) \le k$$\end{document} is an NP-complete problem, even when restricted to bipartite graphs.
Keywords:
Transit function
Stress interval
Stress convexity
Stress number
Stress hull number
Journal
B
IF:
0.8
Papers:
46
Citations:
0
Organization
View more organizations