For graphs H 1 , H 2 , … , H k , the induced Ramsey number IR H 1 , H 2 , … , H k is the smallest integer N , for which there exists a graph G of order N such that any edge coloring of G by k colors contains a monochromatic induced copy of H i in the i th color with 1 ≤ i ≤ k . In this paper, we obtain the exact values or bounds for the multicolor induced Ramsey numbers of stars, matchings, and complete graphs. By Lovász local lemma, we get a lower bound for the induced Ramsey number of general graphs.

Let $G$ be a graph and $S\subseteq V(G)$ with $|S|\geq 2$. Then the trees $T_1, T_2, \cdots, T_\ell$ in $G$ are \emph{internally disjoint Steiner trees} connecting $S$ (or $S$-Steiner trees) if $E(T_i) \cap E(T_j )=\emptyset$ and $V(T_i)\cap V(T_j)=S$ for every pair of distinct integers $i,j$, $1 \leq i, j \leq \ell$. Similarly, if we only have the condition $E(T_i) \cap E(T_j )=\emptyset$ but without the condition $V(T_i)\cap V(T_j)=S$, then they are \emph{edge-disjoint Steiner trees}. The \emph{generalized $k$-connectivity}, denoted by $κ_k(G)$, of a graph $G$, is defined as $κ_k(G)=\min\{κ_G(S)|S \subseteq V(G) \ \textrm{and} \ |S|=k \}$, where $κ_G(S)$ is the maximum number of internally disjoint $S$-Steiner trees. The \emph{generalized local edge-connectivity} $λ_{G}(S)$ is the maximum number of edge-disjoint Steiner trees connecting $S$ in $G$. The {\it generalized $k$-edge-connectivity} $λ_k(G)$ of $G$ is defined as $λ_k(G)=\min\{λ_{G}(S)\,|\,S\subseteq V(G) \ and \ |S|=k\}$. These measures are generalizations of the concepts of connectivity and edge-connectivity, and they and can be used as measures of vulnerability of networks. It is, in general, difficult to compute these generalized connectivities. However, there are precise results for some special classes of graphs. In this paper, we obtain the exact value of $λ_{k}(S(n,\ell))$ for $3\leq k\leq \ell^n$, and the exact value of $κ_{k}(S(n,\ell))$ for $3\leq k\leq \ell$, where $S(n, \ell)$ is the Sierpiński graphs with order $\ell^n$. As a direct consequence, these graphs provide additional interesting examples when $λ_{k}(S(n,\ell))=κ_{k}(S(n,\ell))$. We also study the some network properties of Sierpiński graphs. Steiner Tree; Generalized Connectivity; Sierpiński Graph

Foucaud et al. recently introduced and initiated the study of a new graph-theoretic concept in the area of network monitoring. Given a graph G = ( V( G), E( G)), a set M ⊆ V( G) is a distance-edge-monitoring set if for every edge e ∈ E( G), there is a vertex x ∈ M and a vertex y ∈ V( G) such that the edge e belongs to all shortest paths between x and y. The smallest size of such a set in G is denoted by dem( G). Denoted by G – e (resp. G\ u) the subgraph of G obtained by removing the edge e from G (resp. a vertex u together with all its incident edges from G). In this paper, we first show that dem( G – e) – dem( G) ≤ 2 for any graph G and edge e ∈ E( G). Moreover, the bound is sharp. Next, we construct two graphs G and H to show that dem( G) – dem( G\ u) and dem( H \ v) – dem( H) can be arbitrarily large, where u ∈ V( G) and v ∈ V( H). We also study the relation between dem( H) and dem( G), where H is a subgraph of G. In the end, we give an algorithm to judge whether the distance-edge-monitoring set still remain in the resulting graph when any edge of a graph G is deleted.

Connectivity is one of important parameters for the fault tolerant of an interconnection network. In 1996, Fàbrega and Fiol proposed the concept of g-extra connectivity. A subset of vertices S is said to be a cutset if G−S is not connected. A cutset S is called an Rg-cutset, where g is a non-negative integer, if every component of G−S has at least g+1 vertices. If G has at least one Rg-cutset, the g-extra connectivity of G, denoted by κg(G), is then defined as the minimum cardinality over all Rg-cutsets of G. In this paper, we first obtain the exact value of g-extra connectivity for the lexicographic product of two general graphs. Next, the upper and lower sharp bounds of g-extra connectivity for the Cartesian product of two general graphs are given. In the end, we apply our results on grid graphs and 2-dimensional generalized hypercubes.

International audience

In this paper, we consider the perfect demand matching problem ( PDM ) which combines aspects of the knapsack problem along with the b -matching problem. It is a generalization of the maximum weight matching problem which has been fundamental in the development of theory of computer science and operations research . This problem is NP-hard and there exists a constant ϵ > 0 such that the problem admits no 1 + ϵ -approximation algorithm, unless P=NP. Here, we investigate the performance of a distributed message passing algorithm called Max-sum belief propagation for computing the problem of finding the optimal perfect demand matching. As the main result, we demonstrate the rigorous theoretical analysis of the Max-sum BP algorithm for PDM , and establish that within pseudo-polynomial-time, our algorithm could converge to the optimal solution of PDM , provided that the optimal solution of its LP relaxation is unique and integral. Different from the techniques used in previous literature, our analysis is based on primal-dual complementary slackness conditions , and thus the number of iterations of the algorithm is independent of the structure of the given graph. Moreover, to the best of our knowledge, this is one of a very few instances where BP algorithm is proved correct for NP-hard problems.

BACKGROUND: Drug-Drug interactions (DDIs) are a challenging problem in drug research. Drug combination therapy is an effective solution to treat diseases, but it can also cause serious side effects. Therefore, DDIs prediction is critical in pharmacology. Recently, researchers have been using deep learning techniques to predict DDIs. However, these methods only consider single information of the drug and have shortcomings in robustness and scalability. RESULTS: In this paper, we propose a multi-type feature fusion based on graph neural network model (MFFGNN) for DDI prediction, which can effectively fuse the topological information in molecular graphs, the interaction information between drugs and the local chemical context in SMILES sequences. In MFFGNN, to fully learn the topological information of drugs, we propose a novel feature extraction module to capture the global features for the molecular graph and the local features for each atom of the molecular graph. In addition, in the multi-type feature fusion module, we use the gating mechanism in each graph convolution layer to solve the over-smoothing problem during information delivery. We perform extensive experiments on multiple real datasets. The results show that MFFGNN outperforms some state-of-the-art models for DDI prediction. Moreover, the cross-dataset experiment results further show that MFFGNN has good generalization performance. CONCLUSIONS: Our proposed model can efficiently integrate the information from SMILES sequences, molecular graphs and drug-drug interaction networks. We find that a multi-type feature fusion model can accurately predict DDIs. It may contribute to discovering novel DDIs.