Let $G$ be a graph with vertex set $V$. Two disjoint sets $V_1, V_2 \subseteq V$ form a coalition in $G$ if none of them is a dominating set of $G$ but their union $V_1\cup V_2$ is. A vertex partition $\Psi=\{V_1,\ldots, V_k\}$ of $V$ is called a coalition partition of $G$ if every set $V_i\in \Psi$ is either a dominating set of $G$ with the cardinality $|V_i|=1$, or is not a dominating set but for some $V_j\in \Psi$, $V_i$ and $V_j$ form a coalition. The maximum cardinality of a coalition partition of $G$ is called the coalition number of $G$, denoted by $\mathcal{C}(G)$. A $\mathcal{C}(G)$-partition is a coalition partition of $G$ with cardinality $\mathcal{C}(G)$. Given a coalition partition $\Psi=\{V_1, V_2,\ldots, V_r\}$ of $G$, a coalition graph $CG(G, \Psi)$ is associated on $\Psi$ such that there is a one-to-one correspondence between its vertices and the members of $\Psi$. Two vertices of $CG(G, \Psi)$ are adjacent if and only if the corresponding sets form a coalition in $G$. In this paper, we first show that for any graph $G$ with $\delta(G)=1$, $\mathcal{C}(G)\leq 2\Delta(G)+2$, where $\delta(G)$ and $\Delta(G)$ are the minimum degree and the maximum degree of $G$, respectively. Moreover, we characterize all graphs $G$ with $\delta(G)\leq 1$ and $\mathcal{C}(G)=n$, where $n$ is the number of vertices of $G$. Furthermore, we characterize all trees $T$ with $\mathcal{C}(T)=n$ and all trees $T$ with $\mathcal{C}(T)=n-1$. This solves partially one of the open problem posed in \cite{coal0}. On the other hand, we theoretically and empirically determine the number of coalition graphs that can be defined by all coalition partitions of a given path $P_k$. Furthermore, we show that there is no universal coalition path, a path whose coalition partitions defines all possible coalition graphs. These solve two open problems posed by Haynes et al. \cite{coal1}.
相關內容
We consider a participatory budgeting problem in which each voter submits a proposal for how to divide a single divisible resource (such as money or time) among several possible alternatives (such as public projects or activities) and these proposals must be aggregated into a single aggregate division. Under $\ell_1$ preferences -- for which a voter's disutility is given by the $\ell_1$ distance between the aggregate division and the division he or she most prefers -- the social welfare-maximizing mechanism, which minimizes the average $\ell_1$ distance between the outcome and each voter's proposal, is incentive compatible (Goel et al. 2016). However, it fails to satisfy the natural fairness notion of proportionality, placing too much weight on majority preferences. Leveraging a connection between market prices and the generalized median rules of Moulin (1980), we introduce the independent markets mechanism, which is both incentive compatible and proportional. We unify the social welfare-maximizing mechanism and the independent markets mechanism by defining a broad class of moving phantom mechanisms that includes both. We show that every moving phantom mechanism is incentive compatible. Finally, we characterize the social welfare-maximizing mechanism as the unique Pareto-optimal mechanism in this class, suggesting an inherent tradeoff between Pareto optimality and proportionality.
We study edge-labelings of the complete bidirected graph $\overset{\tiny\leftrightarrow}{K}_n$ with functions from the set $[d] = \{1, \dots, d\}$ to itself. We call a cycle in $\overset{\tiny\leftrightarrow}{K}_n$ a fixed-point cycle if composing the labels of its edges results in a map that has a fixed point, and we say that a labeling is fixed-point-free if no fixed-point cycle exists. For a given $d$, we ask for the largest value of $n$, denoted $R_f(d)$, for which there exists a fixed-point-free labeling of $\overset{\tiny\leftrightarrow}{K}_n$. Determining $R_f(d)$ for all $d >0$ is a natural Ramsey-type question, generalizing some well-studied zero-sum problems in extremal combinatorics. The problem was recently introduced by Chaudhury, Garg, Mehlhorn, Mehta, and Misra, who proved that $d \leq R_f(d) \leq d^4+d$ and showed that the problem has close connections to EFX allocations, a central problem of fair allocation in social choice theory. In this paper we show the improved bound $R_f(d) \leq d^{2 + o(1)}$, yielding an efficient ${{(1-\varepsilon)}}$-EFX allocation with $n$ agents and $O(n^{0.67})$ unallocated goods for any constant $\varepsilon \in (0,1/2]$; this improves the bound of $O(n^{0.8})$ of Chaudhury, Garg, Mehlhorn, Mehta, and Misra. Additionally, we prove the stronger upper bound $2d-2$, in the case where all edge-labels are permulations. A very special case of this problem, that of finding zero-sum cycles in digraphs whose edges are labeled with elements of $\mathbb{Z}_d$, was recently considered by Alon and Krivelevich and by M\'{e}sz\'{a}ros and Steiner. Our result improves the bounds obtained by these authors and extends them to labelings from an arbitrary (not necessarily commutative) group, while also simplifying the proof.
A finite dynamical system with $n$ components is a function $f:X\to X$ where $X=X_1\times\dots\times X_n$ is a product of $n$ finite intervals of integers. The structure of such a system $f$ is represented by a signed digraph $G$, called interaction graph: there are $n$ vertices, one per component, and the signed arcs describe the positive and negative influences between them. Finite dynamical systems are usual models for gene networks. In this context, it is often assumed that $f$ is {\em degree-bounded}, that is, the size of each $X_i$ is at most the out-degree of $i$ in $G$ plus one. Assuming that $G$ is connected and that $f$ is degree-bounded, we prove the following: if $G$ is not a cycle, then $f^{n+1}$ may be a constant. In that case, $f$ describes a very simple dynamics: a global convergence toward a unique fixed point in $n+1$ iterations. This shows that, in the degree-bounded case, the fact that $f$ describes a complex dynamics {\em cannot} be deduced from its interaction graph. We then widely generalize the above result, obtaining, as immediate consequences, other limits on what can be deduced from the interaction graph only, as the following weak converses of Thomas' rules: if $G$ is connected and has a positive (negative) cycle, then $f$ may have two (no) fixed points.
A bipartite graph $G=(A,B,E)$ is ${\cal H}$-convex, for some family of graphs ${\cal H}$, if there exists a graph $H\in {\cal H}$ with $V(H)=A$ such that the set of neighbours in $A$ of each $b\in B$ induces a connected subgraph of $H$. Many $\mathsf{NP}$-complete problems, including problems such as Dominating Set, Feedback Vertex Set, Induced Matching and List $k$-Colouring, become polynomial-time solvable for ${\mathcal H}$-convex graphs when ${\mathcal H}$ is the set of paths. In this case, the class of ${\mathcal H}$-convex graphs is known as the class of convex graphs. The underlying reason is that the class of convex graphs has bounded mim-width. We extend the latter result to families of ${\mathcal H}$-convex graphs where (i) ${\mathcal H}$ is the set of cycles, or (ii) ${\mathcal H}$ is the set of trees with bounded maximum degree and a bounded number of vertices of degree at least $3$. As a consequence, we can re-prove and strengthen a large number of results on generalized convex graphs known in the literature. To complement result (ii), we show that the mim-width of ${\mathcal H}$-convex graphs is unbounded if ${\mathcal H}$ is the set of trees with arbitrarily large maximum degree or an arbitrarily large number of vertices of degree at least $3$. In this way we are able to determine complexity dichotomies for the aforementioned graph problems. Afterwards we perform a more refined width-parameter analysis, which shows even more clearly which width parameters are bounded for classes of ${\cal H}$-convex graphs.
A partition $\mathcal{P}$ of a weighted graph $G$ is $(\sigma,\tau,\Delta)$-sparse if every cluster has diameter at most $\Delta$, and every ball of radius $\Delta/\sigma$ intersects at most $\tau$ clusters. Similarly, $\mathcal{P}$ is $(\sigma,\tau,\Delta)$-scattering if instead for balls we require that every shortest path of length at most $\Delta/\sigma$ intersects at most $\tau$ clusters. Given a graph $G$ that admits a $(\sigma,\tau,\Delta)$-sparse partition for all $\Delta>0$, Jia et al. [STOC05] constructed a solution for the Universal Steiner Tree problem (and also Universal TSP) with stretch $O(\tau\sigma^2\log_\tau n)$. Given a graph $G$ that admits a $(\sigma,\tau,\Delta)$-scattering partition for all $\Delta>0$, we construct a solution for the Steiner Point Removal problem with stretch $O(\tau^3\sigma^3)$. We then construct sparse and scattering partitions for various different graph families, receiving many new results for the Universal Steiner Tree and Steiner Point Removal problems.
Given a weighted graph $G=(V,E,w)$, a partition of $V$ is $\Delta$-bounded if the diameter of each cluster is bounded by $\Delta$. A distribution over $\Delta$-bounded partitions is a $\beta$-padded decomposition if every ball of radius $\gamma\Delta$ is contained in a single cluster with probability at least $e^{-\beta\cdot\gamma}$. The weak diameter of a cluster $C$ is measured w.r.t. distances in $G$, while the strong diameter is measured w.r.t. distances in the induced graph $G[C]$. The decomposition is weak/strong according to the diameter guarantee. Formerly, it was proven that $K_r$ minor free graphs admit weak decompositions with padding parameter $O(r)$, while for strong decompositions only $O(r^2)$ padding parameter was known. Furthermore, for the case of a graph $G$, for which the induced shortest path metric $d_G$ has doubling dimension $d$, a weak $O(d)$-padded decomposition was constructed, which is also known to be tight. For the case of strong diameter, nothing was known. We construct strong $O(r)$-padded decompositions for $K_r$ minor free graphs, matching the state of the art for weak decompositions. Similarly, for graphs with doubling dimension $d$ we construct a strong $O(d)$-padded decomposition, which is also tight. We use this decomposition to construct $\left(O(d),\tilde{O}(d)\right)$-sparse cover scheme for such graphs. Our new decompositions and cover have implications to approximating unique games, the construction of light and sparse spanners, and for path reporting distance oracles.
Proteins can exhibit dynamic structural flexibility as they carry out their functions, especially in binding regions that interact with other molecules. For the key SARS-CoV-2 spike protein that facilitates COVID-19 infection, studies have previously identified several such highly flexible regions with therapeutic importance. However, protein structures available from the Protein Data Bank are presented as static snapshots that may not adequately depict this flexibility, and furthermore these cannot keep pace with new mutations and variants. In this paper we present a sequential Monte Carlo method for broadly sampling the 3-D conformational space of protein structure, according to the Boltzmann distribution of a given energy function. Our approach is distinct from previous sampling methods that focus on finding the lowest-energy conformation for predicting a single stable structure. We exemplify our method on the SARS-CoV-2 omicron variant as an application of timely interest. Our results identify sequence positions 495-508 as a key region where omicron mutations have the most impact on the space of possible conformations, which coincides with the findings of other preliminary studies on the binding properties of the omicron variant.
For two graphs $G^<$ and $H^<$ with linearly ordered vertex sets, the \emph{ordered Ramsey number} $r_<(G^<,H^<)$ is the minimum $N$ such that every red-blue coloring of the edges of the ordered complete graph on $N$ vertices contains a red copy of $G^<$ or a blue copy of $H^<$. For a positive integer $n$, a \emph{nested matching} $NM^<_n$ is the ordered graph on $2n$ vertices with edges $\{i,2n-i+1\}$ for every $i=1,\dots,n$. We improve bounds on the ordered Ramsey numbers $r_<(NM^<_n,K^<_3)$ obtained by Rohatgi, we disprove his conjecture by showing $4n+1 \leq r_<(NM^<_n,K^<_3) \leq (3+\sqrt{5})n$ for every $n \geq 6$, and we determine the numbers $r_<(NM^<_n,K^<_3)$ exactly for $n=4,5$. As a corollary, this gives stronger lower bounds on the maximum chromatic number of $k$-queue graphs for every $k \geq 3$. We also prove $r_<(NM^<_m,K^<_n)=\Theta(mn)$ for arbitrary $m$ and $n$. We expand the classical notion of Ramsey goodness to the ordered case and we attempt to characterize all connected ordered graphs that are $n$-good for every $n\in\mathbb{N}$. In particular, we discover a new class of ordered trees that are $n$-good for every $n \in \mathbb{N}$, extending all the previously known examples.
For an integer $k \geq 1$ and a graph $G$, let $\mathcal{K}_k(G)$ be the graph that has vertex set all proper $k$-colorings of $G$, and an edge between two vertices $\alpha$ and~$\beta$ whenever the coloring~$\beta$ can be obtained from $\alpha$ by a single Kempe change. A theorem of Meyniel from 1978 states that $\mathcal{K}_5(G)$ is connected with diameter $O(5^{|V(G)|})$ for every planar graph $G$. We significantly strengthen this result, by showing that there is a positive constant $c$ such that $\mathcal{K}_5(G)$ has diameter $O(|V(G)|^c)$ for every planar graph $G$.
In this work we propose and unify classes of different models for information propagation over graphs. In a first class, propagation is modeled as a wave which emanates from a set of known nodes at an initial time, to all other unknown nodes at later times with an ordering determined by the time at which the information wave front reaches nodes. A second class of models is based on the notion of a travel time along paths between nodes. The time of information propagation from an initial known set of nodes to a node is defined as the minimum of a generalized travel time over subsets of all admissible paths. A final class is given by imposing a local equation of an eikonal form at each unknown node, with boundary conditions at the known nodes. The solution value of the local equation at a node is coupled the neighbouring nodes with smaller solution values. We provide precise formulations of the model classes in this graph setting, and prove equivalences between them. Motivated by the connection between first arrival time model and the eikonal equation in the continuum setting, we demonstrate that for graphs in the particular form of grids in Euclidean space mean field limits under grid refinement of certain graph models lead to Hamilton-Jacobi PDEs. For a specific parameter setting, we demonstrate that the solution on the grid approximates the Euclidean distance.
注冊地址： 北京市海淀區羊坊店路18號2幢3層301-191