搜索结果：connected

The connected coalition in a graph $G=(V,E)$ consists of two disjoint sets of vertices $V_{1}$ and $V_{2}$, neither of which is a connected dominating set but whose union $V_{1}\cup V_{2}$, is a connected dominating set. A connected coalition partition in a graph $G$ of order $n=|V|$ is a vertex partition $ψ$ = $\{V_1, V_2,..., V_k \}$ such that every set $V_i \in ψ$ either is a connected dominating set consisting of a single vertex of degree $n-1$, or is not a connected dominating set but forms a connected coalition with another set $V_j\in ψ$ which is not a connected dominating set. The connected coalition number, denoted by $CC(G)$, is the maximum cardinality of a connected coalition partition of $G$. In this paper, we initiate the study of connected coalition in graphs and present some basic results. Precisely, we characterize all graphs that have a connected coalition partition. Moreover, we show that for any graph $G$ of order $n$ with $δ(G)=1$ and with no full vertex, it holds that $CC(G)<n$. Furthermore, we show that for any tree $T$, $CC(T)=2$. Finally, we present two polynomial-time algorithms that for a given connected graph $G$ of order $n$ determine whether $CC(G)=n

For a graph $G=(V,E)$, a pair of vertex disjoint sets $A_{1}$ and $A_{2}$ form a connected coalition of $G$, if $A_{1}\cup A_{2}$ is a connected dominating set, but neither $A_{1}$ nor $A_{2}$ is a connected dominating set. A connected coalition partition of $G$ is a partition $Φ$ of $V(G)$ such that each set in $Φ$ either consists of only a singe vertex with the degree $|V(G)|-1$, or forms a connected coalition of $G$ with another set in $Φ$. The connected coalition number of $G$, denoted by $CC(G)$, is the largest possible size of a connected coalition partition of $G$. In this paper, we characterize graphs that satisfy $CC(G)=2$. Moreover, we obtain the connected coalition number for unicycle graphs and for the corona product and join of two graphs. Finally, we give a lower bound on the connected coalition number of the Cartesian product and the lexicographic product of two graphs.

Though a convergence space is connected if and only if its topological modification is connected, connected subsets differ for the convergence and for its topological modification. We explore for what subsets connectedness for the convergence or for the topological modification turn out to be equivalent. In particular, we show that the largest set containing a given connected set for which all subsets in between are connected is the adherence of the connected set for the reciprocal modification of the convergence.

Cooperative driving enabled by connected and automated vehicles is expected to improve traffic efficiency and safety, particularly at intersections where traditional control mechanisms such as traffic lights introduce delays and unnecessary stops. Although cooperative intersection management algorithms have been widely studied, experimental demonstrations remain limited. This paper presents a real-time demonstration of cooperative intersection management using connected autonomous mini-cars. The testbed consists of multiple 1:10 scale vehicles equipped with autonomous driving capabilities and wireless communication modules that interact with a centralized controller responsible for scheduling their crossing of the intersection. Vehicles approaching the intersection exchange messages with the controller to set the appropriate mobility profile to traverse the intersection without stopping. The demonstration integrates autonomous driving, wireless communication, and cooperative control in a single experimental platform, providing a practical environment for validating cooperative intersection management concepts for future intelligent transportation systems.

The classical theorem due to Győri and Lovász states that any $k$-connected graph $G$ admits a partition into $k$ connected subgraphs, where each subgraph has a prescribed size and contains a prescribed vertex, as long as the total size of target subgraphs is equal to the size of $G$. However, this result is notoriously evasive in terms of efficient constructions, and it is still unknown whether such a partition can be computed in polynomial time, even for $k = 5$. We make progress towards an efficient constructive version of the Győri--Lovász theorem by considering a natural strengthening of the $k$-connectivity requirement. Specifically, we show that the desired connected partition can be found in polynomial time, if $G$ contains $k$ disjoint connected dominating sets. As a consequence of this result, we give several efficient approximate and exact constructive versions of the original Győri--Lovász theorem: 1. On general graphs, a Győri--Lovász partition with $k$ parts can be computed in polynomial time when the input graph has connectivity $Ω(k \cdot \log^2 n)$; 2. On convex bipartite graphs, connectivity of $4k$ is sufficient; 3. On biconvex graphs and interval graphs, connect

For $N>1$, we constructed a canonical connected fundamental domain for $Γ_0(N)$ in [Nie, Parent], utilizing an interesting function $W: {\mathbb Z}/N\to {\mathbb N}$. In this paper, we further study the function $W$, prove some identities, and use it to match the cusps, with widths, produced by our connected fundamental domain with the known cusp classes of $Γ_0(N)$. Furthermore, we list the boundary arcs and the gluing patterns of our connected fundamental domain, a key step in understanding the modular curve $X_0(N)$ by this approach.

We address Gromov's band width inequality and Rosenberg's $S^1$-stability conjecture for simply connected smooth four manifolds. Both results are known to be false in dimension 4 due to counterexamples based on Seiberg-Witten invariants. Nevertheless we show that both of these results hold upon considering simply connected smooth four manifolds up to homeomorphism. We also obtain a related result for non-simply connected smooth four manifolds.

Objective sleep assessment relies on polysomnography (PSG), yet clinical impact is often better reflected in patient-reported outcomes (PROs) such as sleepiness and fatigue. Existing summary indices, including the Apnea-Hypopnea Index (AHI), provide limited insight into the multidomain physiology underlying functional recovery. We propose an interpretable, causal-discovery--guided framework for deriving a hierarchical Sleep Recovery Score (SRS) from multimodal PSG. Using two large population cohorts (MESA: n=1540; MrOS: n=825), we apply directed acyclic graph (DAG) learning to identify candidate physiological drivers spanning respiratory burden, hypoxic burden, sleep fragmentation, sleep architecture, and autonomic regulation. Although derived from clinical PSG, these domains map naturally to sensing streams increasingly available in connected health technologies, including wearable ECG, oximetry, and sleep-stage estimation devices. To preserve mechanistic plausibility, we introduce a two-stage screening process that combines physiology-based constraints with constrained LLM-assisted auditing to identify and remove structural confounders and construct-overlapping variables. Across

In the emerging mixed traffic environments, Connected and Autonomous Vehicles (CAVs) have to interact with surrounding human-driven vehicles (HDVs). This paper introduces MSH-MCCT (Multi-Source Human-in-the-Loop Mixed Cloud Control Testbed), a novel CAV testbed that captures complex interactions between various CAVs and HDVs. Utilizing the Mixed Digital Twin concept, which combines Mixed Reality with Digital Twin, MSH-MCCT integrates physical, virtual, and mixed platforms, along with multi-source control inputs. Bridged by the mixed platform, MSH-MCCT allows human drivers and CAV algorithms to operate both physical and virtual vehicles within multiple fields of view. Particularly, this testbed facilitates the coexistence and real-time interaction of physical and virtual CAVs \& HDVs, significantly enhancing the experimental flexibility and scalability. Experiments on vehicle platooning in mixed traffic showcase the potential of MSH-MCCT to conduct CAV testing with multi-source real human drivers in the loop through driving simulators of diverse fidelity. The videos for the experiments are available at our project website: https://dongjh20.github.io/MSH-MCCT.

This paper focuses on energy-efficient longitudinal controller design for a connected automated truck that travels in mixed traffic consisting of connected and non-connected vehicles. The truck has access to information about connected vehicles beyond line of sight using vehicle-to-vehicle (V2V) communication. A novel connected cruise control design is proposed which incorporates additional delays into the control law when responding to distant connected vehicles to account for the finite propagation of traffic waves. The speeds of non-connected vehicles are modeled as stochastic processes. A fundamental theorem is proven which links the spectral properties of the motion signals to the average energy consumption. This enables us to tune controller parameters and maximize energy efficiency. Simulations with synthetic data and real traffic data are used to demonstrate the energy efficiency of the control design. It is demonstrated that even with lean penetration of connected vehicles, our controller can bring significant energy savings.

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.

Let $G$ be a connected graph with minimum degree $δ(G)$ and vertex-connectivity $κ(G)$. The graph $G$ is $k$-connected if $κ(G)\geq k$, maximally connected if $κ(G) = δ(G)$, and super-connected (or super-$κ$) if every minimum vertex-cut isolates a vertex of minimum degree. In this paper, we show that a connected graph or a connected triangle-free graph is $k$-connected, maximally connected or super-connected if the number of edges or the spectral radius is large enough.

Let X=(V, E) be a digraph. X is maximally connected, if κ(X)=δ(X). X is maximally arc-connected, if λ(X)=δ(X). And X is super arc-connected, if every minimum arc-cut of X is either the set of inarcs of some vertex or the set of outarcs of some vertex. In this paper, we will prove that the strongly connected Bi-Cayley digraphs are maximally connected and maximally arc-connected, and the most of strongly connected Bi-Cayley digraphs are super arc-connected.

The proper connection number $pc(G)$ of a connected graph $G$ is defined as the minimum number of colors needed to color its edges, so that every pair of distinct vertices of $G$ is connected by at least one path in $G$ such that no two adjacent edges of the path are colored the same, and such a path is called a proper path. In this paper, we show that for every connected graph with diameter 2 and minimum degree at least 2, its proper connection number is 2. Then, we give an upper bound $\frac{3n}{δ+ 1}-1$ for every connected graph of order $n$ and minimum degree $δ$. We also show that for every connected graph $G$ with minimum degree at least $2$, the proper connection number $pc(G)$ is upper bounded by $pc(G[D])+2$, where $D$ is a connected two-way (two-step) dominating set of $G$. Bounds of the form $pc(G)\leq 4$ or $pc(G)=2$, for many special graph classes follow as easy corollaries from this result, which include connected interval graphs, asteroidal triple-free graphs, circular arc graphs, threshold graphs and chain graphs, all with minimum degree at least $2$. Furthermore, we get the sharp upper bound 3 for the proper connection numbers of interval graphs and circular arc gr

This paper investigates distributed computing and cooperative control of connected and automated vehicles (CAVs) in ramp merging scenario under transportation cyber-physical system. Firstly, a centralized cooperative trajectory planning problem is formulated subject to the safely constraints and traffic performance in ramp merging scenario, where the trajectories of all vehicles are jointly optimized. To get rid of the reliance on a central controller and reduce computation time, a distributed solution to this problem implemented among CAVs through Vehicles-to-Everything (V2X) communication is proposed. Unlike existing method, our method can distribute the computational task among CAVs and carry out parallel solving through V2X communication. Then, a multi-vehicles model predictive control (MPC) problem aimed at maximizing system stability and minimizing control input is formulated based on the solution of the first problem subject to strict safety constants and input limits. Due to these complex constraints, this problem becomes high-dimensional, centralized, and non-convex. To solve it in a short time, a decomposition and convex reformulation method, namely distributed cooperativ

We show that if a closed oriented $n$-manifold $M$ has a non-trivial cohomology class of even degree $k$, whose all pullbacks to products of type $S^1\times N$ vanish, then the topological complexity $\mathrm{TC}(M)$ is at least $6$, if $n$ is odd, and at least $7$ or $9$, if $n$ is even. These bounds extend and improve a result of Mescher and apply for instance to negatively curved manifolds and to connected sums with at least one such summand. In fact, better bounds are obtained due to the non-vanishing of the Gromov norm. As a consequence, in dimension four, we completely determine the topological complexity of these connected sums, namely we show that it is equal to its maximum value nine. Furthermore, we discuss realisation of degree two homology classes by tori, and show how to construct non-realisable classes out of realisable classes in connected sums. The examples of this paper will quite often be aspherical manifolds whose fundamental groups have trivial center and connected sums. We thus discuss the possible relation between the maximum topological complexity $2n+1$ and the triviality of the center for aspherical $n$-manifolds and their connected sums.

A symplectic manifold is called symplectic rationally connected if there is a non-zero genus zero Gromov-Witten invariant with two point insertions. It is conjectured that every smooth projective rationally connected variety is symplectic rationally connected. In this short note we give some examples of rationally connected 4-folds which are symplectic rationally connected. In particular, all Fano 4-folds of pseudo-index at least 2 are symplectic rationally connected. The proof does not use any explicit description of these varieties.

The connected tree-width of a graph is the minimum width of a tree-decomposition whose parts induce connected subgraphs. Long cycles are examples of graphs that have small tree-width but large connected tree-width. We show that a graph has small connected tree-width if and only if it has small tree-width and contains no long geodesic cycle. We further prove a connected analogue of the duality theorem for tree-width: a finite graph has small connected tree-width if and only if it has no bramble whose connected covers are all large. Both these results are qualitative: the bounds are good but not tight. We show that graphs of connected tree-width $k$ are $k$-hyperbolic, which is tight, and that graphs of tree-width $k$ whose geodesic cycles all have length at most $\ell$ are $\lfloor{3\over2}\ell(k-1)\rfloor$-hyperbolic. The existence of such a function $h(k,\ell)$ had been conjectured by Sullivan.

Rainbow connection number rc(G) of a connected graph G is the minimum number of colours needed to colour the edges of G, so that every pair of vertices is connected by at least one path in which no two edges are coloured the same. In this paper we show that for every connected graph G, with minimum degree at least 2, the rainbow connection number is upper bounded by γ_c(G) + 2, where γ_c(G) is the connected domination number of G. Bounds of the form diameter(G) \leq rc(G) \leq diameter(G) + c, 1 \leq c \leq 4, for many special graph classes follow as easy corollaries from this result. This includes interval graphs, AT-free graphs, circular arc graphs, threshold graphs, and chain graphs all with minimum degree at least 2 and connected. We also show that every bridge-less chordal graph G has rc(G) \leq 3.radius(G). In most of these cases, we also demonstrate the tightness of the bounds. An extension of this idea to two-step dominating sets is used to show that for every connected graph on n vertices with minimum degree δ, the rainbow connection number is upper bounded by 3n/(δ + 1) + 3. This solves an open problem of Schiermeyer (2009), improving the previously best known bound of 20