Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userRoots of Two-Terminal Reliability
59
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Assume that the vertices of a graph $G$ are always operational, but the edges of $G$ are operational independently with probability $p in[0,1]$. For fixed vertices $s$ and $t$, the emph{two-terminal reliability} of $G$ is the probability that the operational subgraph contains an $(s,t)$-path, while the emph{all-terminal reliability} of $G$ is the probability that the operational subgraph contains a spanning tree. Both reliabilities are polynomials in $p$, and have very similar behaviour in many respects. However, unlike all-terminal reliability, little is known about the roots of two-reliability polynomials. In a variety of ways, we shall show that the nature and location of the roots of two-terminal reliability polynomials have significantly different properties than those held by roots of the all-terminal reliability.
rate research
Read More
Assume that the vertices of a graph $G$ are always operational, but the edges of $G$ fail independently with probability $q in[0,1]$. The emph{all-terminal reliability} of $G$ is the probability that the resulting subgraph is connected. The all-terminal reliability can be formulated into a polynomial in $q$, and it was conjectured cite{BC1} that all the roots of (nonzero) reliability polynomials fall inside the closed unit disk. It has since been shown that there exist some connected graphs which have their reliability roots outside the closed unit disk, but these examples seem to be few and far between, and the roots are only barely outside the disk. In this paper we generalize the notion of reliability to simplicial complexes and matroids and investigate when, for small simplicial complexes and matroids, the roots fall inside the closed unit disk.
In this short note we observe that recent results of Abert and Hubai and of Csikvari and Frenkel about Benjamini--Schramm continuity of the holomorphic moments of the roots of the chromatic polynomial extend to the theory of dense graph sequences. We offer a number of problems and conjectures motivated by this observation.
We show that a monic univariate polynomial over a field of characteristic zero, with $k$ distinct non-zero known roots, is determined by its $k$ proper leading coefficients by providing an explicit algorithm for computing the multiplicities of each root. We provide a version of the result and accompanying algorithm when the field is not algebraically closed by considering the minimal polynomials of the roots. Furthermore, we show how to perform the aforementioned algorithm in a numerically stable manner over $mathbb{C}$, and then apply it to obtain new characteristic polynomials of hypergraphs.
We find precise asymptotic estimates for the number of planar maps and graphs with a condition on the minimum degree, and properties of random graphs from these classes. In particular we show that the size of the largest tree attached to the core of a random planar graph is of order c log(n) for an explicit constant c. These results provide new information on the structure of random planar graphs.
In this paper, we discuss maximality of Seidel matrices with a fixed largest eigenvalue. We present a classification of maximal Seidel matrices of largest eigenvalue $3$, which gives a classification of maximal equiangular lines in a Euclidean space with angle $arccos1/3$. Motivated by the maximality of the exceptional root system $E_8$, we define strong maximality of a Seidel matrix, and show that every Seidel matrix achieving the absolute bound is strongly maximal.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
