The practical utility of a quantum network depends on its ability to establish entanglement between arbitrary node pairs with quality sufficient to execute entanglement enabled tasks. This capability can be assessed globally, through aggregate performance over all node pairs, as well as locally, at the level of individual nodes. Since entanglement-based connections form a layer above the underlying physical topology, quantum connectivity is not adequately captured by classical topological connectivity metrics. To enable characterisation of the quantum connectivity at the level of the network (or its subnetworks), we introduce the quantum connectivity measure (QCM), which quantifies the average connection quality between pairs of network nodes. Further, we describe two quantities, the quantum-connected fraction (QCF) and the quantum clustering coefficient (QCC), naturally derived from the QCM, which capture important features of the functional connectivity of the quantum network at the level of the network and an individual node, respectively. These metrics of quantum connectivity depend crucially on the entanglement distribution protocol and the quantum network parameters in additi
In this paper, we explore a taxonomy of connectivity for space-like structures. It is inspired by isolating posets of connected pieces of a space and examining its embedding in the ambient space. The taxonomy includes in its scope all standard notions of connectivity in point-set and point-free contexts, such as connectivity in graphs and hypergraphs (as well as k-connectivity in graphs), connectivity and path-connectivity in topology, and connectivity of elements in a frame.
In several applications in distributed systems, an important design criterion is ensuring that the network is sparse, i.e., does not contain too many edges, while achieving reliable connectivity. Sparsity ensures communication overhead remains low, while reliable connectivity is tied to reliable communication and inference on decentralized data reservoirs and computational resources. A class of network models called random K-out graphs appear widely as a heuristic to balance connectivity and sparsity, especially in settings with limited trust, e.g., privacy-preserving aggregation of networked data in which networks are deployed. However, several questions remain regarding how to choose network parameters in response to different operational requirements, including the need to go beyond asymptotic results and the ability to model the stochastic and adversarial environments. To address this gap, we present theorems to inform the choice of network parameters that guarantee reliable connectivity in regimes where nodes can be finite or unreliable. We first derive upper and lower bounds for probability of connectivity in random K-out graphs when the number of nodes is finite. Next, we an
This article investigates the connectivity dimension of a graph. We introduce this concept in analogy to the metric dimension of a graph, providing a graph parameter that measures the heterogeneity of the connectivity structure of a graph. We fully characterize extremal examples and present explicit constructions of infinitely many graphs realizing any prescribed non-extremal connectivity dimension. We also establish a general lower bound in terms of the graph's block structure, linking the parameter to classical notions from graph theory. Finally, we prove that the problem of computing the connectivity dimension is NP-complete.
Millimeter wave (mmWave) 5th generation (5G) networks offer high data rates but face coverage challenges due to severe path loss and blockage. These problems motivate the use of Integrated Access and Backhaul (IAB) as a flexible wireless backhaul solution that extends connectivity to cell boundaries and unfibered areas, including maritime environments. This paper overviews the latest 3GPP specifications for IAB networks in Releases 16 through 18. Then, it presents an ns-3 module for IAB, featuring a complete end-to-end protocol stack, including the backhaul adaptation protocol (BAP) layer, flexible slot and control configurations, and multiplexing schemes based on both time and frequency division. We test the IAB module via extensive system-level simulations in a custom maritime scenario where vessels, equipped with IAB-nodes, can simultaneously act as access points and relays, forming dynamic multi-hop networks that maintain connectivity via wireless backhaul to shore-based stations. We evaluate different topologies and channel conditions, providing insights into the design and deployment of mmWave IAB networks in offshore environments.
It is well-known that functions over finite fields play a crucial role in designing substitution boxes (S-boxes) in modern block ciphers. In order to analyze the security of an S-box, recently, three new tables have been introduced: the Extended Boomerang Connectivity Table (EBCT), the Lower Boomerang Connectivity Table (LBCT), and the Upper Boomerang Connectivity Table (UBCT). In fact, these tables offer improved methods over the usual Boomerang Connectivity Table (BCT) for analyzing the security of S-boxes against boomerang-style attacks. Here, we put in context these new EBCT, LBCT, and UBCT concepts by connecting them to the DDT for a differentially $δ$-uniform function and also determine the EBCT, LBCT, and UBCT entries of three classes of differentially $4$-uniform power permutations, namely, Gold, Kasami and Bracken-Leander. We also determine the Double Boomerang Connectivity Table (DBCT) entries of the Gold function. As byproducts of our approach, we obtain some previously published results quite easily.
The connectivity of a graph is an important parameter to evaluate its reliability. $k$-restricted connectivity (resp. $R^h$-restricted connectivity) of a graph $G$ is the minimum cardinality of a set $S$ of vertices in $G$, if exists, whose deletion disconnects $G$ and leaves each component of $G-S$ with more than $k$ vertices (resp. $δ(G-S)\geq h$). In contrast, structure (substructure) connectivity of $G$ is defined as the minimum number of vertex-disjoint subgraphs whose deletion disconnects $G$. As generalizations of the concept of connectivity, structure (substructure) connectivity, restricted connectivity and $R^h$-restricted connectivity have been extensively studied from the combinatorial point of view. Very little is known about the computational complexity of these variants, except for the recently established NP-completeness of $k$-restricted edge-connectivity. In this paper, we prove that the problems of determining structure, substructure, restricted, and $R^h$-restricted connectivity are all NP-complete.
The paper introduces two player connectivity games played on finite bipartite graphs. Algorithms that solve these connectivity games can be used as subroutines for solving Müller games. Müller games constitute a well established class of games in model checking and verification. In connectivity games, the objective of one of the players is to visit every node of the game graph infinitely often. The first contribution of this paper is our proof that solving connectivity games can be reduced to the incremental strongly connected component maintenance (ISCCM) problem, an important problem in graph algorithms and data structures. The second contribution is that we non-trivially adapt two known algorithms for the ISCCM problem to provide two efficient algorithms that solve the connectivity games problem. Finally, based on the techniques developed, we recast Horn's polynomial time algorithm that solves explicitly given Müller games and provide an alternative proof of its correctness. Our algorithms are more efficient than that of Horn's algorithm. Our solution for connectivity games is used as a subroutine in the algorithm.
Let $G = (V, E)$ be a graph with non-empty set of vertices $V$ and set of edges $E$. The \emph{eccentric connectivity index} of the graph $G$ is defined as $$\displaystyle{ξ^C(G) = \sum_{u \in V} d_u \;ecc(u)}$$ where $d_u$ is the degree and $ecc(u)$ is the eccentricity of the vertex $u \in V$. This article is an attempt to find the \emph{eccentric connectivity index} of strongly connected digraph $D$ with respect to the metric, \textit{maximum distance} defined by $md(u,v)=\max\{\vec{d}(u,v),\vec{d}(v,u)\}$. An attempt is also made to find the extremal values for strongly connected digraphs.
Despite intensive research in the area of network connectivity, there is an important category of problems that remain unsolved: how to measure the quality of connectivity of a wireless multi-hop network which has a realistic number of nodes, not necessarily large enough to warrant the use of asymptotic analysis, and has unreliable connections, reflecting the inherent unreliable characteristics of wireless communications? The quality of connectivity measures how easily and reliably a packet sent by a node can reach another node. It complements the use of \emph{capacity} to measure the quality of a network in saturated traffic scenarios and provides a native measure of the quality of (end-to-end) network connections. In this paper, we explore the use of probabilistic connectivity matrix as a possible tool to measure the quality of network connectivity. Some interesting properties of the probabilistic connectivity matrix and their connections to the quality of connectivity are demonstrated. We argue that the largest eigenvalue of the probabilistic connectivity matrix can serve as a good measure of the quality of network connectivity.
Background: During an experimental session, behavioral performance fluctuates, yet most neuroimaging analyses of functional connectivity derive a single connectivity pattern. These conventional connectivity approaches assume that since the underlying behavior of the task remains constant, the connectivity pattern is also constant. New Method: We introduce a novel method, behavior-regressed connectivity (BRC), to directly examine behavioral fluctuations within an experimental session and capture their relationship to changes in functional connectivity. This method employs the weighted phase lag index (WPLI) applied to a window of trials with a weighting function. Using two datasets, the BRC results are compared to conventional connectivity results during two time windows: the one second before stimulus onset to identify predictive relationships, and the one second after onset to capture task-dependent relationships. Results: In both tasks, we replicate the expected results for the conventional connectivity analysis, and extend our understanding of the brain-behavior relationship using the BRC analysis, demonstrating subject-specific connectivity patterns that correspond to both posi
This paper presents some basic facts about the so-called connectivity spaces. In particular, it studies the generation of connectivity structures, the existence of limits and colimits in the main categories of connectivity spaces, the closed monoidal category structure given by the so-called tensor product on integral connectivity spaces; it defines homotopy for connectivity spaces and mention briefly related difficulties; it defines smash product of pointed integral connectivity spaces and shows that this operation results in a closed monoidal category with such spaces as objects. Then, it studies finite connectivity spaces, associating a directed acyclic graph with each such space and then defining a new numerical invariant for links: the connectivity order. Finally, it mentions the not very wellknown Brunn-Debrunner-Kanenobu theorem which asserts that every finite integral connectivity space can be represented by a link.
Aerial base stations (ABSs) mounted on unmanned aerial vehicles (UAVs) are capable of extending wireless connectivity to ground users (GUs) across a variety of scenarios. However, it is an NP-hard problem with exponential complexity in $M$ and $N$, in order to maximize the coverage rate (CR) of $M$ GUs by jointly placing $N$ ABSs with limited coverage range. The complexity of the problem escalates in environments where the signal propagation is obstructed by localized obstacles such as buildings, and is further compounded by the dynamic GU positions. In response to these challenges, this paper focuses on the optimization of a multi-ABS movement problem, aiming to improve the mean CR for mobile GUs within a site-specific environment. Our proposals include 1) introducing the concept of global connectivity map (GCM) which contains the connectivity information between given pairs of ABS/GU locations; 2) partitioning the ABS movement problem into ABS placement sub-problems and formulate each sub-problem into a binary integer linear programming (BILP) problem based on GCM; 3) and proposing a fast online algorithm to execute (one-pass) projected stochastic subgradient descent within the d
This note investigates the connectivity of $τ$-tilting graphs for algebras from the point of view of quotients. We establish the connectivity of $τ$-tilting graph for an arbitrary quasi-tilted algebra and prove that the connectivity of the $τ$-tilting graph of a $g$-tame algebra is preserved under quotient. In particular, quotient algebras of skew-gentle algebras and quotient algebras of tame hereditary algebras have connected $τ$-tilting graphs.
Short cycles connectivity is a generalization of ordinary connectivity. Instead by a path (sequence of edges), two vertices have to be connected by a sequence of short cycles, in which two adjacent cycles have at least one common vertex. If all adjacent cycles in the sequence share at least one edge, we talk about edge short cycles connectivity. It is shown that the short cycles connectivity is an equivalence relation on the set of vertices, while the edge short cycles connectivity components determine an equivalence relation on the set of edges. Efficient algorithms for determining equivalence classes are presented. Short cycles connectivity can be extended to directed graphs (cyclic and transitive connectivity). For further generalization we can also consider connectivity by small cliques or other families of graphs.
A {\em connectivity function on} a set $E$ is a function $λ:2^E\rightarrow \mathbb R$ such that $λ(\emptyset)=0$, that $λ(X)=λ(E-X)$ for all $X\subseteq E$ and that $λ(X\cap Y)+λ(X\cup Y)\leq λ(X)+λ(Y)$ for all $X,Y \subseteq E$. Graphs, matroids and, more generally, polymatroids have associated connectivity functions. We introduce a notion of duality for polymatroids and prove that every connectivity function is the connectivity function of a self-dual polymatroid. We also prove that every integral connectivity function is the connectivity function of a half-integral self-dual polymatroid.
Dynamic connectivity is a well-studied problem, but so far the most compelling progress has been confined to the edge-update model: maintain an understanding of connectivity in an undirected graph, subject to edge insertions and deletions. In this paper, we study two more challenging, yet equally fundamental problems. Subgraph connectivity asks to maintain an understanding of connectivity under vertex updates: updates can turn vertices on and off, and queries refer to the subgraph induced by "on" vertices. (For instance, this is closer to applications in networks of routers, where node faults may occur.) We describe a data structure supporting vertex updates in O (m^{2/3}) amortized time, where m denotes the number of edges in the graph. This greatly improves over the previous result [Chan, STOC'02], which required fast matrix multiplication and had an update time of O(m^0.94). The new data structure is also simpler. Geometric connectivity asks to maintain a dynamic set of n geometric objects, and query connectivity in their intersection graph. (For instance, the intersection graph of balls describes connectivity in a network of sensors with bounded transmission radius.) Previously
The eccentric connectivity index, proposed by Sharma, Goswami and Madan, has been employed successfully for the development of numerous mathematical models for the prediction of biological activities of diverse nature. We now report mathematical properties of the eccentric connectivity index. We establish various lower and upper bounds for the eccentric connectivity index in terms of other graph invariants including the number of vertices, the number of edges, the degree distance and the first Zagreb index. We determine the n-vertex trees of diameter with the minimum eccentric connectivity index, and the n-vertex trees of pendent vertices, with the maximum eccentric connectivity index. We also determine the n-vertex trees with respectively the minimum, second-minimum and third-minimum, and the maximum, second-maximum and third-maximum eccentric connectivity indices for
For Boolean satisfiability problems, the structure of the solution space is characterized by the solution graph, where the vertices are the solutions, and two solutions are connected iff they differ in exactly one variable. For this implicitly defined graph, we here study the st-connectivity and connectivity problems. Building on the work of Gopalan et al. ("The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies", 2006/2009), we first investigate satisfiability problems given by CSPs, more exactly CNF(S)-formulas with constants (as considered in Schaefer's famous 1978 dichotomy theorem); we prove a computational dichotomy for the st-connectivity problem, asserting that it is either solvable in polynomial time or PSPACE-complete, and an aligned structural dichotomy, asserting that the maximal diameter of connected components is either linear in the number of variables, or can be exponential; further, we show a trichotomy for the connectivity problem, asserting that it is either in P, coNP-complete, or PSPACE-complete. Next we investigate two important variants: CNF(S)-formulas without constants, and partially quantified formulas; in both cases, we prove
The eccentric connectivity index $ξ^c$ is a novel distance--based molecular structure descriptor that was recently used for mathematical modeling of biological activities of diverse nature. It is defined as $ξ^c (G) = \sum_{v \in V (G)} deg (v) \cdot ε(v)$\,, where $deg (v)$ and $ε(v)$ denote the vertex degree and eccentricity of $v$\,, respectively. We survey some mathematical properties of this index and furthermore support the use of eccentric connectivity index as topological structure descriptor. We present the extremal trees and unicyclic graphs with maximum and minimum eccentric connectivity index subject to the certain graph constraints. Sharp lower and asymptotic upper bound for all graphs are given and various connections with other important graph invariants are established. In addition, we present explicit formulae for the values of eccentric connectivity index for several families of composite graphs and designed a linear algorithm for calculating the eccentric connectivity index of trees. Some open problems and related indices for further study are also listed.