Scattering number and τ \tau -toughness in graphs involving A α A_{\alpha} -spectral radius This work is supported by the National Natural Science Foundations of China (No. 12371348, 12201258), the Postgraduate Research & Practice Innovation Program of Jiangsu Normal University (No. 2025XKT0632, 202

Caili Jia, Yong Lu · 2025

Read Scattering number and τ \tau -toughness in graphs involving A α A_{\alpha} -spectral radius This work is supported by the National Natural Science Foundations of China (No. 12371348, 12201258), the Postgraduate Research & Practice Innovation Program of Jiangsu Normal University (No. 2025XKT0632, 202 by Caili Jia, Yong Lu (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-2509-01050.txt.

Introduction

Caili Jia and Yong Lu work on graph theory, the math of networks made of points and links. They study two measures of how hard a graph is to break apart. The scattering number counts pieces left after points are removed, while tau-toughness weighs removals against the pieces they create.

Both measures link to how well a network stays connected after damage. Jia and Lu use a spectral value, a number drawn from a graph matrix, called rho alpha in plain terms. They give a condition that ensures the scattering number stays at one or less. They also give a condition for a graph to count as tau-tough, and both results extend earlier work by Chen, Li, and Xu.

Catalog record

CREATORCaili Jia, Yong Lu
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE37 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-01050

Browse the full library · About the Tower of Babel

Full text

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

Scattering number and τ \tau -toughness in graphs involving A α A_{\alpha} -spectral radius This work is supported by the National Natural Science Foundations of China (No. 12371348, 12201258), the Postgraduate Research & Practice Innovation Program of Jiangsu Normal University (No. 2025XKT0632, 2025XKT0633) . Caili Jia, Yong Lu Abstract Abstract The scattering number s(G) of graph G=(V,E) is defined as s(G) =max { c(G-S)-|S| } , where the maximum is taken over all proper subsets S\subseteq V(G) , and c(G-S) denotes the number of components of G-S . In 1988, Enomoto introduced a variation of toughness \tau(G) of a graph G , which is defined by \tau(G) =min { \frac{|S|}{c(G-S)-1} , S\subseteq V(G) and c(G-S)>1 } . Both the scattering number and toughness are used to characterize the invulnerability or stability of a graph, i.e., the ability of a graph to remain connected after vertices or edges are removed. The smaller the value of s(G) (or the larger the value of \tau(G) ), the stronger the connectivity of a graph G . The A_{\alpha} -spectral radius of G is denoted by \rho_{\alpha}(G) . Using typical A_{\alpha} -spectral techniques and structural analysis, we present a sufficient condition such that s(G)\leq 1 . This result generalizes the result of Chen, Li and Xu [Graphs Comb. 41 (2025)]. Furthermore, we establish a sufficient condition with respect to the A_{\alpha} -spectral radius for a graph to be \tau -tough. When \alpha=\frac{1}{2} , our result reduces to that of Chen, Li and Xu [Graphs Comb. 41 (2025)]. Key Words : Scattering number; \tau -tonghness; A_{\alpha} -spectral. AMS Subject Classification (2010) : 05C35; 05C50. 1 Introduction Throughout this paper, we consider only finite, undirected and simpe graphs. Let G=(V(G),E(G)) be a graph, where V(G) is the vertex set and E(G) is the edge set. The order and size of G are denoted by |V(G)|=n and |E(G)|=m , respectively. Denote by \delta(G) ( \delta for short) and \Delta(G) ( \Delta for short) the minimum degree and the maximum degree of G , respectively. For a vertex subset S of G , we denote by G-S and G[S] the subgraph of G obtained from G by deleting the vertices in S together with their incident edges and the subgraph of G induced by S , respectively. A subgraph of a graph G is spanning if the subgraph covers all vertices of G . The number of components of G is denoted by c(G) . Let G be a graph of order n , and let the adjacency matrix of G be defined as A(G)=(a_{ij})_{n\times n} , where a_{ij}=1 if v_{i}v_{j}\in E(G) , and a_{ij}=0 otherwise. The degree diagonal matrix is the diagonal matrix of vertex degrees of G , denoted by D(G) . The Laplacian matrix L(G) and signless Laplacian matrix Q(G) of G is defined by L(G)=D(G)-A(G) and Q(G)=D(G)+A(G) , respectively. The eigenvalues of A(G) , L(G) and Q(G) are called the eigenvalues , the Laplacian eigenvalues and the signless Laplacian eigenvalues of G , and denoted by \lambda_{1}(G)\geq\lambda_{2}(G)\geq\cdots\geq\lambda_{n}(G) , \mu_{1}(G)\geq\mu_{2}(G)\geq\cdots\geq\mu_{n}(G)=0 and q_{1}(G)\geq q_{2}(G)\geq\cdots\geq q_{n}(G) , respectively. The largest eigenvalues of A(G) , L(G) and Q(G) are also called the spectral radius , Laplacian spectral radius and the signless Laplacian spectral radius of G , and denoted by \lambda(G) , \mu(G) and q(G) , respectively. We sometimes write \lambda_{i} , \mu_{i} and q_{i} to instead of \lambda_{i}(G),\mu_{i}(G) and q_{i}(G) for 1\leq i\leq n . For any \alpha\in[0,1] , Nikiforov [ 31 ] introduced the A_{\alpha} -matrix of G as A_{\alpha}(G)=\alpha D(G)+(1-\alpha)A(G) . One can see that A_{\alpha}(G)=A(G) if \alpha=0 , and A_{\alpha}(G)=\frac{1}{2}Q(G) if \alpha=\frac{1}{2} . Hence, A_{\alpha}(G) generalizes both the adjacency matrix and the signless Laplacian matrix of G . The eigenvalues of A_{\alpha}(G) are called the A_{\alpha} -eigenvalues of G , and the largest of them, denoted by \rho_{\alpha}(G) , is called the A_{\alpha} -spectral radius of G . More interesting spectral properties of A_{\alpha}(G) can be found in [ 5 , 24 , 26 , 27 , 31 , 32 ] . Let t be a positive real number and a connected graph G is t -tough if tc(G-S)\leq|S| for every vertex cut S of V(G) . The toughness of graph G , denoted by t(G) , is the largest value of t for which G is t -tough (taking t(K_{n})=\infty where K_{n} is a complete graph of order n ). Thus, t(G)=\min\{\frac{|S|}{c(G-S)}:S\subseteq V(G),c(G-S)>1\} . The concept of toughness initially proposed by Chvátal [ 11 ] in 1973, which serves as a simple way to measure how tightly various pieces of a graph hold together. The toughness is related to many other important properties of a graph, such as the existence of factors [ 4 , 6 , 12 , 13 , 15 , 29 ] , cycles [ 17 ] and spanning trees [ 2 ] . For more extensive work on toughness, one can see [ 3 , 10 , 28 , 30 , 35 , 36 ] . In order to better investigate the existence of factors in a graph, Enomoto [ 13 ] introduced a slight variation of toughness in 1998. A non-complete graph G is \tau -tough if |S|\geq\tau(c(G-S)-1) for every proper subset S\subseteq V(G) with c(G-S)>1 . The variation of toughness \tau(G) of G is the maximum \tau for which G is \tau -tough. Thus, \tau(G)=\min\{\frac{|S|}{c(G-S)-1}:S\subseteq V(G),c(G-S)>1\} in which the minimum is taken over all proper sets S\subseteq V(G) . For two vertex-disjoint graphs G_{1} and G_{2} , we use G_{1}\cup G_{2} to denote the disjoint union of G_{1} and G_{2} . The join G_{1}\vee G_{2} is the graph obtained from G_{1}\cup G_{2} by adding all possible edges between V(G_{1}) and V(G_{2}) . In [ 11 ] , Chvátal conjectured that every k -tough graph on n\geq k+1 vertices and kn even contains a k -factor. Enomoto et al. [ 15 ] gave a decisive answer to Chvátal’s conjecture. In [ 12 ] , Enomoto strengthened the result obtained by Enomoto et al. [ 15 ] . In 1998, this result was first improved by Enomoto [ 13 ] by using the definition of \tau(G) . Enomoto and Hagita [ 14 ] were able to generalize the results in [ 13 ] and strengthened the results in [ 15 ] with a sufficiently large number of vertices. The scattering number of a graph G was defined by Jung [ 23 ] as s(G) =max { c(G-S)-|S|:S\subseteq V(G),c(G-S)>1 } . It is clear that the concept of a scattering number is similar to that of toughness in some sense. Hendry [ 21 ] proposed s(G)\leq 0 is one necessary condition for Hamiltonian since s(G)\leq 0 is equivalent to t(G)\geq 1 . For any graph G the condition s(G)\leq 1 is equivalent to the condition \tau(G)\geq 1 . Both the scattering number and toughness are used to characterize the invulnerability or stability of a graph, i.e., the ability of the graph to remain connected after vertices or edges are removed. The parameter of scattering number has a strong background of applications in measuring network vulnerability [ 33 ] . Unlike the connectivity measures, it takes account not only the difficulty to destroy a network, but also what remains after the network

Read the complete text