Printer Friendly

Connected tropical subgraphs in vertex-colored graphs.

A subgraph of a vertex-colored graph is said to be tropical whenever it contains each color of the graph. In this work we study the problem of finding a minimal connected tropical subgraph. We first show that this problem is NP-Hard for trees, interval graphs and split graphs, but polynomial when the number of colors is logarithmic in terms of the order of the graph (i.e. FPT). We then provide upper bounds for the order of the minimal connected tropical subgraph under various conditions. We finally study the problem of finding a connected tropical subgraph in a randomly vertex-colored random graph.

Keywords: vertex-colored graph, connected subgraph, tropical subgraph, colorful subgraph, vertex-colored random graph.

1 Introduction

In this work, we deal with tropical substructures in vertex-colored graphs, first introduced in [AMK+]. Vertex-colored graphs are useful in various situations. For instance, the Web graph may be considered as a vertex-colored graph where the color of a vertex represents the content of the corresponding page (red for mathematics, yellow for physics, etc.) [BHKN13]. Applications can also be found in bioinformatics (Multiple Sequence Alignment Pipeline or for multiple protein-protein Interaction networks) [CPM10]. Given a vertex-colored graph, a tropical subgraph is defined to be a subgraph where each color of the initial graph appears at least once. Potentially, many graph invariants, such as the domination number and the vertex cover number, can be studied in their tropical version. This notion is close to the colorful concept used for paths in vertex-colored graphs [ALN11, Li01, Lin07] (with a colorful path being a tropical subgraph that is a path, and has no repeat color), though works on colored paths usually focus on finding colorings that fulfill specific criteria, one being admitting colorful path, while our work consider the coloring as an inherent property of the graph. It is also related to the concepts of color patterns used in bio-informatics [FFHV11, ZSLS11], which share our approach for the coloring of the graph. Here, we study minimum connected tropical subgraphs in vertex-colored graphs, focusing especially on the case where the number of colors used is large. The case where the number of colors is small is even more interesting in view of the aforementioned applications. Some related work can also be found in [BHKN13, BHK+12, PA, ZSLS11], where the authors are looking for the minimum number of edges to delete in a graph such that all remaining connected components are colorful (i.e., do not contain two vertices of the same color). Some ongoing work on dominating tropical sets, tropical paths and tropical homomorphisms can be found in [AMK+, FHH+].

Throughout the paper, we let G = (V, E) denote a simple undirected graph. Given a set of colors C = {1,... , c}, [G.sup.c] denotes a vertex-colored graph whose vertices are each colored (not necessarily properly) by one of the colors in C, and each color of C colors at least one vertex. For any subgraph H of [G.sup.c], we denote by c(H) the set of colors of the vertices of H. A graph [G.sup.c] is said to be properly colored when no adjacent vertices have the same color. The chromatic number of an uncolored graph G, denoted [chi](G), is the smallest number of colors c such that there exists a graph [G.sup.c] that is properly colored. A connected subgraph H of [G.sup.c] is said to be tropical if c(H) = C. The connected tropical subgraph number tc([G.sup.c]) is the order of a smallest connected tropical subgraph of [G.sup.c]. A connected rainbow subgraph of [G.sup.c] is a connected subgraph in which each color is present at most once. A connected colorful subgraph of [G.sup.c] is a connected rainbow subgraph which is tropical. The neighborhood N(u) is the set containing all vertices adjacent to vertex u in [G.sup.c]. The degree d(u) is the number of vertices in N(u). The closed neighborhood N[u] is N(u) [union] {u}. We let [delta]([G.sup.c]) denote the minimum degree of [G.sup.c]. When no confusion arises, we write tc and [delta] instead of tc([G.sup.c]) and [delta]([G.sup.c]). A dominating set S of a graph G = (V, E) is a subset of V such that every vertex of V is either in S, or adjacent to a vertex in S. We denote by [gamma](G) the minimum size of a dominating set of G. We call blocks of a graph its maximal 2-connected subgraphs, and say that a block is a leaf block when it contains exactly one cut-vertex. This paper is a study of the following problem:

MINIMUM CONNECTED TROPICAL SUBGRAPH PROBLEM (MCTS)

Input: A connected vertex-colored graph [G.sup.c], and an integer k.

Question: Is there a connected tropical subgraph of order k in [G.sup.c]?

It is split into three parts. In Section 2 we prove that MCTS is NP-complete for general graphs, trees, interval and split graphs. We also give a dynamic programming FPT (Fixed Parameter Tractable) algorithm parametrized in the number of colors for general graphs. In Section 3 we give upper bounds for tc related to various parameters (minimum degree, number of edges). In Section 4, we study how tc behaves on random graphs.

2 NP-Har[d.sub.n]ess and FPT algorithms

Theorem 2.1. MCTS is NP-Complete on trees.

Proof: MCTS is in NP since testing whether a given set of vertices corresponds to a tropical connected subgraph can be done in polynomial time. The reduction is obtained from DOMINATING SET on general graphs. Consider an instance of DOMINATING SET on a graph G with vertices [v.sub.1], [v.sub.2],... , [v.sup.n]. We define a colored tree [T.sup.c] with n + 2 colors [c.sup.1], [c.sup.2],... , [c.sub.n+2] in the following way. Let r be a vertex of color [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and for each i [member of] {1,... , n}:

* Let si be a vertex of color [c.sub.n+2] adjacent to r.

* Let s be a vertex of color [c.sub.i] adjacent to [s.sub.i].

* For each vertex [v.sub.j] [member of] N([v.sub.i]), there is a vertex of color [c.sup.j] adjacent to [s'.sub.i].

[ILLUSTRATION OMITTED]

Given a dominating set S of G, along with a function f associating to each vertex v [member of] G | S an element of S that dominates it, we define a connected tropical subgraph H of [T.sup.c], containing the following vertices:

1. The vertex r.

2. The vertices si and s of [T.sup.c] for every [v.sub.i] [member of] S.

3. For each vertex [v.sub.i] [member of] G | S, we take the vertex of color ci which is adjacent to the vertex s' such that vj = f([v.sub.i]).

By construction, H is connected and tropical.

Reciprocally, given a minimal connected tropical subgraph H of [T.sup.c], we define the following set of vertices and f function: [v.sub.i] belongs to S if and only if s| [member of] H, and for each vj [member of] S, f(vj) = [v.sub.i] where i is such that s is the neighbor of the only vertex of color [c.sup.j] in H. Hence, there exists a bijection between a pair (S, f) associated with a dominant S of G and a minimal connected tropical subgraph H of [T.sup.c]. Moreover, we have the following:

|H| = 1 + 2|S| + n - |S| = 1 + |S| + n.

Thus, by considering the minimum cardinality of S, we obtain,

tc([T.sup.c]) = 1 + [gamma](G) + n.

As a result, a minimum connected tropical subgraph of [T.sup.c] corresponds to a minimum dominating set of G. Clearly, the reduction from the dominating set problem is in polynomial time, and the theorem is proved. []

By the reduction, it follows that MCTS is NP-complete even when restricted to trees of height 3.

We recall that a graph G is called an interval graph if one can assign to each v in V an interval Iv [subset] R such that [I.sub.u] [intersection] [I.sub.v] is nonempty if and only if uv [member of] E.

Theorem 2.2. MCTS is NP-Hard for interval graphs, even when restrict[e.sub.d] to connect[e.sub.d] colorful subgraphs.

Proof: As not[e.sub.d] in the proof of Theorem 2.1, MCTS is in NP. We will show it is NP-hard by a r[e.sub.d]uction from the VERTEX COVER problem (VC). Consider an instance of VC on a graph G with n vertices and m [e.sub.d]ges and an integer k. To this instance we will associate a set of color[e.sub.d] intervals. We introduce first the colors as follows. The colors are

* for each [e.sub.d]ge e = (u, v) [member of] E, two colors [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

* for each vertex u [member of] V , a color cu, and

* colors [c.sub.left] and [c.sub.right].

The set of intervals will be partition[e.sub.d] into subsets, call[e.sub.d] gadgets, and those gadgets will be order[e.sub.d]. The intervals which right extremity is the rightmost of gadget j will intersect with the intervals which left extremity is the leftmost of gadget j + 1. Apart from this rule, intervals will only intersect with other intervals from the same gadget. The very first gadget is going to contain only one interval of color [c.sub.left], and the very last gadget is going to contain only one interval of color [c.sub.right]. In between, there will be a number of gadgets from the following three types, whose respective order do not matter for the proof.

Type 1: For each vertex v in V , the gadget [g.sub.v] is defin[e.sub.d] as follows. Let [e.sub.1], [e.sub.2], [e.sub.3],... , [e.sub.d](v) be the [e.sub.d]ges adjacent to v. There are d(v) intervals of color [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and one interval of color The interval of color [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] intersects only the interval of color [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], the interval of color [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (when those intervals exist), and the interval of color [c.sup.v]. The intervals [c.sup.v] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (respectively [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] ) have the same leftmost (respectively rightmost) extremity. For instance, if v is a vertex of degree four, the intervals are defin[e.sub.d] as follows.

[ILLUSTRATION OMITTED]

An interval will intersect with some intervals from the previous (respectively next) gadget if and only if it crosses the left (respectively right) dott[e.sub.d] line.

Type 2: For each [e.sub.d]ge e = uv in E, gadget g'e is defin[e.sub.d] as follows. There are two intervals of color [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] which share both their left and their right boundaries.

[ILLUSTRATION OMITTED]

Type 3: The last type of gadget g" uses n intervals with the same boundaries and colors [c.sup.v1], [c.sup.v2],... , [c.sup.vn], as follows.

[ILLUSTRATION OMITTED]

So, there are n gadgets of type 1 (one for each vertex of G), m gadgets of type 2 (one for each edge of G), and we include n - k gadgets of type 3. Figure 1 illustrates the r[e.sub.d]uction. Let us consider the interval graph impli[e.sub.d] by the obtained set of intervals. By coloring each vertex from this interval graph with the color of the corresponding interval, we obtain a vertex-color[e.sub.d] interval graph [I.sup.c].

[FIGURE 1 OMITTED]

Let S be a vertex cover of G of size k. We will show a connected colorful subgraph of [I.sup.c] can be build from S. Consider the set W of vertices from [I.sup.c] associat[e.sub.d] to the following intervals:

* The two intervals of color [c.sub.left] and [c.sub.right],

* for each vertex u [member of] S, we take the intervals of color cu from the type 1 gadget corresponding to u, along with all the intervals of color [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] from the type 2 gadgets,

* for each vertex vi among {[v.sub.1], [v.sub.2],... , vn-k} = V| S, we take all the intervals of color [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] from the type 1 gadget corresponding to vi, along with the vertex of color cvi from the i-th gadget of type 3.

By construction, the obtained set of intervals will include exactly one interval of each color. Let us show that the union of all the intervals in the set is connected. To do so, let us show that for every gadget, we have intervals in W whose union is covering the whole gadget. This is the case directly for gadgets of type 1. This is the case for a gadget of type 2 because there is always at least one endpoint of the corresponding edge that belongs to S. This is also the case for gadgets of type 3 because there are exactly n - k vertices in G | S. Therefore, the set of vertices in [I.sup.c] associat[e.sub.d] to this set of intervals is a connected colorful subgraph.

Let T be a set of intervals that correspond to a connected colorful subgraph of [I.sup.c]. We will show how T implies a vertex cover of G of size k. We consider the set S of vertices of G such that a vertex u is in S if and only if there exists an edge e of G such that T contains the interval of color [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] from gadget g'(e).

By construction of [I.sup.c], there is only one vertex of [I.sup.c] with color [c.sub.left], and one with color [c.sub.right]. Therefore, any connected subgraph of [I.sup.c] must contain those two vertices. As the subgraph ne[e.sub.d]s to be connected, it must also contain a path linking those two vertices. Therefore, for every gadget, the union of the intervals of T must include the whole gadget.

Let us consider the gadget g'(e) for some edge e of G with e = (u, v). The set T must contain either the interval of color [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] or the interval of color [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Therefore, at least one of the endpoints of e must be includ[e.sub.d] in S. The set S is hence a vertex cover.

Consider now the gadgets of type 3. The set T must contain an interval from each of those n - k gadgets, and each of those intervals must be of a different color. Hence there are n - k vertices [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] such that T contains an interval of color cui in a gadget of type 3.

Finally, consider the gadget g(u) for some vertex u of G adjacent to edges[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. The set T must contain either the interval of color cu or all the intervals of color [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. If S contains the vertex v, it means there exists some i such that T contains an interval of color [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] from a gadget of type 2. As T contains exactly one interval of each color, it means that T cannot contain the interval of color [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] in g(u). As intervals of T must cover the whole of the gadget g(u), T contains the interval of color cu. This means that T does not contain another interval of color cu from another gadget. As T already contains intervals of color [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] this means S can contain at most k vertices. []

A graph G is called a split graph if V can be partition[e.sub.d] into sets [V.sub.0] and [V.sub.1] such that the subgraphs induced by [V.sub.0], and [V.sub.1], are a clique and an independent set, respectively.

Theorem 2.3. MCTS is NP-Hardfor split graphs.

Proof: We show that a polynomial algorithm for MCTS on split graphs can be used to solve VERTEX COVER on all graphs. To a given graph G with n vertices and m edges, we associate the vertex-colored split graph [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] defin[e.sub.d] as follows:

* For each vertex v) of G there is in SG a vertex [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. All vertices [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII](v) are pairwise adjacent, and are colored with color c0 .

* For each edge uv of G there is in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] a vertex [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII](uv) adjacent to [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII](u) and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII](v). Each vertex [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII](uv) is colored with a unique color.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] is a split graph colored with m + 1 colors, and we can partition the set of vertices of SG into sets [V.sub.0] and [V.sub.1] where [V.sub.o] is the set of vertices of color c0 (which induce a clique) and [V.sub.1] is the set of the remaining vertices (which induce an independent set). We show that a bijection exists between the set of minimum connected tropical subgraphs of SG and the set of optimal solutions to VERTEX COVER in G.

Let X be the vertices of a minimum connected tropical subgraph in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. As V| C X, let us write [V.sub.2] = X|V1. Observe that [V.sub.2] defines a vertex cover in G. Inde[e.sub.d], X is connected in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and so [V.sub.2] contains at least one of [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] or [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] for every [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. On the other hand, every vertex cover of G of cardinality k defines in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] a tropical set of cardinality k + m, which is necessarily connected as V0 is a clique. Consequently, computing the minimum connected tropical subgraph in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] determines the minimum Vertex Cover of G. []

Theorem 2.4. MCTS can be solv[e.sub.d] in O(n2 [chi] m [chi] 8c) time, where n and m are respectively the number of vertices and edges of Gc.

Proof: We show that we can compute for each vertex u [member of] [G.sub.C] the function [f.sub.u] : P(C) [right arrow] {1,... , n} which associates to a set of color S the order of the smallest connected subgraph containing u and at least one vertex of each color in S. The optimal value of MCTS is then the smallest value [f.sub.v] (C) reach[e.sub.d] for any vertex v. The algorithm is the following :

* Step 1: For u [member of] V, initialize [f.sub.u](S) := 1 when S = {c(u)} and [f.sub.u](S) := n otherwise.

* Step 2: While there exists an edge e = uv in [G.sub.c] and two sets of colors [S.sub.u], [S.sub.v] [member of] P(C) such that [f.sub.u]([S.sub.u]) + [f.sub.v]([S.sub.v]) < [f.sub.u]([S.sub.u] [union] [S.sub.v]), update [f.sub.u] by setting [f.sub.u]([S.sub.u] [union] [S.sub.v]) := [f.sub.u]([S.sub.u]) + [f.sub.v]([S.sub.v]).

Let us prove that the algorithm above is correct. Let us first show, by induction on the number of iterations, that at any iteration of Step 2, if [f.sub.u](S) = k, then there exists a connected subgraph of [G.sub.c] of order k that contains at least one vertex of each color in S. After Step 1, {u} is a suitable subgraph if S = {c(u)}, and [G.sub.c] itself is suitable otherwise. Now suppose that the property is true before some iteration of Step two on edge uv of the algorithm. Let [H.sub.u] (respectively, [H.sub.v]), be the subgraph of order [f.sub.u]([S.sub.u]) (respectively, [f.sub.v]([S.sub.v])) containing u, (respectively, v), and at least one vertex of each color in [S.sub.u] (respectively, [S.sub.v]). By taking the union of [H.sub.u] and [H.sub.v], we obtain a subgraph of order at most [f.sub.u]([S.sub.u]) + [f.sub.v]([S.sub.v]) containing every color in [S.sub.u] [union] [S.sub.v]. This proves the claim. Hence, for every vertex u in [G.sub.c], tc([G.sub.c]) [less than or equal to] [f.sub.u](C).

We will show that the comput[e.sub.d] values of [f.sub.u] correspond to the definition we gave of the function. Let us suppose, for contradiction, that at the end of the algorithm there is a vertex u and a connected subgraph H of order k containing u such that k < [f.sub.u](c(H)). Consider a spanning tree T of H root[e.sub.d] at u. For a vertex v in T, we denote by T(v) the subtree of T root[e.sub.d] at v. Now, we claim that for every vertex v in T, [f.sub.v](c(T(v))) [greater than or equal to] |T(v)|. This is obvious if v is a leaf, as in this case T(v) = {v}, and [f.sub.v]({c(v)}) = 1 by Step 1 of the algorithm. Thus, we may suppose that the claim is true for all children [v.sub.1],... , [v.sub.r] of a vertex v, and show that it holds for v. Since we can not apply Step 2 of the algorithm on the edge v[v.sub.1], with sets c(v) and c(T([v.sub.1])), it means that [f.sub.v](c(v) [union] c(T([v.sub.1]))) + [f.sub.v](c(v)) + [f.sub.v]!(c(T([v.sub.1]))). We know that c(v) [union] c(T([v.sub.1])) = c(v [union] T([v.sub.1])), [f.sub.v](c(v)) = 1 (by Step 1 of the algorithm) and [f.sub.v]l(c(T([v.sub.1]))) |T([v.sub.1])| (by induction), therefore [f.sub.v](c(v [union] T([v.sub.1]))) 1 + |T([v.sub.1])|. By the same reasoning, since we cannot apply Step 2 of the algorithm on W2, with sets c({v} [union] T([v.sub.1])) and c(T(v2)), it means that [f.sub.v](c(v [union] T([v.sub.1]) [union] T(v2))) - 1 + |T([v.sub.1])| + |T(v2)|. By repeating this argument for each child of v, we obtain that [f.sub.v](c(T(v))) = [f.sub.v](c(v [union] T([v.sub.1]) [union]... [union] T(vj))) 1 + |T([v.sub.1])| +... + |T(vj)| = |T(v)|. Hence for every vertex v in T, [f.sub.v](c(T(v))) |T(v)|. Thus, [f.sub.u](c(H)) = [f.sub.u](c(T(u))) + |T(u)| = k, a contradiction. This proves the correctness of the algorithm.

Let us prove next the complexity of the algorithm. Setting up the initial values of every [f.sub.u](S) in Step 1 can be done in O(n x [2.sup.c]). The identification of an edge uv and two sets [S.sub.u], [S.sub.v], suitable to apply Step 2 of the algorithm, takes at most m x [2.sup.c] x [2.sup.c] operations. Applying Step 2 will strictly decrease the value of [f.sub.u]([S.sub.u] [union] [S.sub.v]). There are only n functions on [2.sup.c] values, and each function can decrease at most n times on each value. Therefore, Step 2 is iterated at most n x [2.sup.c] x n times. So the complexity is at most O([n.sup.2] x m x [8.sup.c]), as required. []

3 Sufficient Conditions

In this section, we give sufficient conditions for a vertex-colored graph to have connected color[f.sub.u]l subgraphs of small order. Our first result relates tc([G.sub.c]) to [chi](G).

Proposition 3.1. If [G.sup.c] is a properly colored graph on [chi](G) colors, then it contains a connected colorful subgraph.

Proof: Let [V.sub.1] CVbea color class of [G.sup.c]. There must exist a vertex v G [V.sub.1] whose neighborhood contains all the other colors, as otherwise all vertices of [V.sub.1] could be recolored with a color that does not appear in their neighborhood, yielding a proper coloring of G with [chi](G) - 1 colors. But now, [G.sup.c][N[v]] contains a connected colorful subgraph. []

Before we prove the next result, we need the following lemma.

Lemma 3.2. Let G be a connected graph with n vertices and m edges. If G contains (at least) i cut vertices then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Proof: We prove the result by induction on i, knowing that it holds when i = 0. We therefore assume that i > 0. Let v be a non-cut vertex from a leaf block of G. If v has degree 1 then G|v has at least i - 1 cut vertices, and by induction

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Otherwise G|v has a set C of at least i cut vertices and v is adjacent with at most one of them. Note, however, that v cannot be adjacent to all of V(G)|C, as every cut vertex splits V(G)|C into (at least) two non-empty connected components. Therefore, v has degree at most (n - i - 2) + 1 = n - i - 1 and by induction

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] []

Theorem 3.3. Let [G.sup.c] be a connected vertex-colored graph with n vertices and m edges. For every non-negative integer k [less than or equal to] n - 4, ifm [less than or equal to] ([MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]) + n - c+ 2, then tc([G.sup.c]) [greater than or equal to] c + k.

Proof: By induction on n. If n [less than or equal to] c + k, then [G.sup.c] itself is a connected tropical subgraph of order at most c + k. We may therefore assume that n [greater than or equal to] c + k +1. Let F [[subset].bar] V be the set of vertices whose colors appear at least twice in the graph. Then |F| [greater than or equal to] n - c + 1 since at most c - 1 colors appear exactly once. Let i = n - c + 1. We have assum[e.sub.d] that k [less than or equal to] n - c - 1, which implies that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Using Lemma 3.2, we know that there is a vertex v [member of] F such that v is not a cut vertex.

We assume first that d(v) [greater than or equal to] n - k - 1. Let N[v] be the clos[e.sub.d] neighborhood of v. Then G | N[v] is of order at most k. Let p be the number of colors in N[v]. We will build a connected tropical subgraph of order at most k + c. First we take v and p - 1 of its neighbors colored with the p - 1 remaining colors.

For each missing color z, we add a connected component H of G | N[v] which contains z and one vertex from the neighborhood of v to keep H connected to v. In the worst case, we add every vertex in the graph G|N[v] andc- p vertices in the neighborhood of v, which yields a connected tropical subgraph of order at most c + k.

Now, assume that d(v) [greater than or equal to] n - k - 2. Let G' = G | {v} on n' vertices and m' edges. Then G' is connected (by definition of v), n! = n - 1, G' is colored with c colors (as v G F) and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

By induction, there exist a connected tropical subgraph of order c + k in G'. It is also a tropical subgraph of order c + kinG. This completes the argument and the proof. []

Note that the above proof leads to a polynomial time algorithm that finds a connected tropical subgraph of order c+k under the hypothesis of the theorem. We now show that the bound given in the above theorem is tight. Fix two positive integers n and k. Consider now a rainbow complete graph [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] on n - k - 2 vertices. Let [x.sub.1] be a vertex of color 1 in [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Add a path [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] Color vk+2 with color 0 and every other vi with color 1. The resulting graph has exactly [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] edges, but has no connected tropical subgraph of order less than c + k + 1.

Theorem 3.4. Let [G.sup.c] be a vertex-colored graph of minimum degree [delta]. If [delta] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] a connected colorful subgraph.

Proof: Let S be the vertices of a largest connected rainbow subgraph of [G.sup.c]. Assume |S| < c, otherwise the proof is done. As |S| < c, there exists a vertex v [member of] [G.sup.c] | S which color does not appear in S. Also v has no neighbor in S, as S is maximal. Now, we distinguish between two cases depending upon the connectivity of S.

Suppose first S is 2-connected. For each vertex u G S, |N(u) [pi] N(v)| > 2, since u and v are not adjacent and [delta] [greater than or equal to] . If a vertex w G N(u) [pi] N (v) is colored with a different color than u, then S can be extend[e.sub.d] to another connected rainbow subgraph, say S', by removing from S at most one vertex of the same color as w and adding to S vertices w and v. As S is 2-connected and only one vertex is removed from S, S' is connected. Furthermore, by definition, S' is rainbow, and |S'| > |S|,a contradiction. Thus, every vertex in N(u) [pi] N (v) has the same color as the vertex u. Since this is true for every u in S, N(v) contains every color in S and there is a connected rainbow subgraph of [G.sup.c] of order |S| + 1 contain[e.sub.d] in N[v], a contradiction to the maximality property of S.

Suppose next S is not 2-connected. Let [union] be a subset of S containing exactly one non-cut vertex from each leaf block of S. We define T = {w|w G V | S, such that w is neighbor of a vertex in S}. Clearly, every color which appears in T also appears in S. This implies that |V | T| [greater than or equal to] c [greater than or equal to] n/2 and, in turn, that |T| [less than or equal to] n/2.

We now consider e(U [union] {v}, T), i.e., the number of edges between [union] [union] {v} and T. Note that a vertex u [member of] [union] contain[e.sub.d] in a leaf block B [[subset].bar] S has at most |B| - 1 neighbors in S. It follows,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Thus, there is a vertex u [member of] T adjacent to at least |U| + 1 vertices in [union] [union] {v}, i.e., to all of them. As u is connected to a non cut-vertex in every leaf block of S, S [union] {u} is 2-connected. Let u' be the vertex of S colored with the same color as u. Then (S | {u'}) [union] {u} [union] {v} is a connected rainbow subgraph of order |S| + 1, a contradiction to the maximality property of S. []

The proof of Theorem 3.4 imm[e.sub.d]iately yields the following.

Corollary 3.5. Let [G.sup.c] be a vertex-colored graph of order n and of minimum degree [delta]. If [delta] [greater than or equal to] n2 and c [greater than or equal to] n, then a connected colorful subgraph can be found in polynomial time.

We let [delta]r([G.sup.c]) denote the minimum rainbow degree of [G.sup.c], i.e., the smallest number of colors a vertex in [G.sup.c] has in its neighborhood.

Theorem 3.6. The following holds:

1. For every e, e' [member of] [0,1), there exists a vertex-colored graph [G.sup.c] such that [delta]([G.sup.c]) [greater than or equal to] en, [delta]r([G.sup.c]) [greater than or equal to] e'c and [G.sup.c] has no connected colorful subgraph.

2. For every positive integer p, there exists a vertex-colored graph [G.sup.c] such that [delta]([G.sup.c]) [greater than or equal to] n - c + p and [G.sup.c] has no connected colorful subgraph.

3. For every positive integer p and e [member of] [0,1), there exists a vertex-colored graph [G.sup.c] such that [delta]([G.sup.c]) [greater than or equal to] en, [G.sup.c] is p-connected and has no connected colorful subgraph.

Proof: Let i, j, k be three positive integers, k [greater than or equal to] 2. We first define an uncolored graph G(i, j, k) that will be used to prove all the three parts of the theorem. The graph G(i,j, k) is defin[e.sub.d] as follows:

* G(i, j, k) is compos[e.sub.d] of k vertex-disjoint cliques H1, H2,... , Hk, each of order i, and k vertexdisjoint cliques D1, D2,... , Dk, each of order j.

* For alll = l', every vertex of Hl is adjacent to every vertex of and to every vertex of Dl. G(i,j, k) has the following properties:

* n = |V(G(i,j, k))| = k(i + j).

* [delta] = (k - 1)i + j - 1.

* G(i,j, k) is i(k - 1)-connected.

By varying i, j, k and the coloring we can prove the three parts of the theorem as follows.

1. We consider G(i,j, k) with each vertex in Hl colored with color 1, for l = 1,... , k. Every Dl contains one vertex of colors 2,3,... j and one vertex of color j + l. The graph G(i,j,k) colored this way is denoted by [G.sup.c]. It satisfies the following properties:

* c = j + k.

* [delta]r([G.sup.c]) = j.

Let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] Then [delta]r([G.sup.c]) = j = e'j + (1 - e')j > e'(j + k) = e'c and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]e when i [right arrow] [infinity]. For i sufficiently large, we have a graph with [delta] > en, [delta]r > e'c. It has no connected colorful subgraph. Indeed, such a tropical subgraph would have to contain a vertex from each Dl. Thus, it would need to contain vertices in at least two Hl. This contradicts the fact that each color is present only once.

2. We consider G(i,j, k) with each vertex in Hl colored with color 1, for l = 1,... , k. Now, color all the jk vertices of the Dl with colors {2, 3,... , jk + 1} so that each color appears on exactly one vertex. Let [G.sup.c] denote the resulting colored graph. Then [G.sup.c] is colored with c = jk + 1 colors.

Given p [member of] N, choose j such that j > i+p. Then [delta]([G.sup.c]) = (k - 1)i+j - 1 > ki+p - 1 = n - c+p. Graph [G.sup.c] has no connected colorful subgraph. Indeed, such a tropical subgraph would need to contain every vertex in each Dl. Thus, it would need to contain vertices in at least two Hl to be connected. This contradicts the fact that each color is present only once.

3. We consider G(i,j, k) colored the same way as in Case 2. Let [G.sup.c] be the obtained graph. Given p [member of] N, and e [member of] [0,1), we choose any j [member of] N, and k such that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] then [G.sup.c] is p-connected. Also [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] when i [right arrow] [infinity]. For i sufficiently large, [G.sup.c] is p-connected with [delta]([G.sup.c]) [greater than or equal to] en. By the argument in Case 2, [G.sup.c] has no connected colorful subgraphs.[]

4 Random graphs

In this section we are interested in the problem of finding particular tropical subgraphs in a random graph such as cliques and connected components. Recall that the random graph G(n, p) is the graph with vertex set V = {1,... , n} in which each of the possible ([MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]) edges appears with probability p, independently. In other words, if G is a graph with vertex set V and has m edges, then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

For more background on random graphs, we refer the reader to [Bol01] and [JLR00].

In our model, we will study a randomly vertex-colored random graph. Given a positive integer c, let G(n,p, c) be the graph obtained from G(n,p) by coloring each vertex with one of the colors 1,2,... , c uniformly and independently at random. The vertex coloring is independent of the existence of edges. Clearly, for any given vertex-colored graph [G.sup.c] on V with m edges, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

We will say that G(n,p, c) has a property Q asymptotically almost surely (abbreviated a.a.s.) if the probability it satisfies Q tends to 1 as n [right arrow] [infinity].

We begin by recalling some notation and results that will be needed. Let X be a random variable. We denote by E(X) and Var(X) the expectation and the variance of X, respectively. For r [greater than or equal to] 0, (n)r = n(n - 1)... (n - r + 1) denotes the falling factorial. E(X)r is called the r-th factorial moment of X. In particular, E(X)o = 1 and E(X)1 = E(X). Let [X.sub.1],[X.sub.2],... ,[X.sub.n] and X be integer-valued random variables. We say that [X.sub.n] converges in distribution to X, as n [right arrow] [infinity], and write [X.sub.n] [right arrow] X, if P[[X.sub.n] = k] [right arrow] P[X = k] for every integer k.

The following useful bound is known as the Chebyshev's inequality which states that, for t > 0

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

In particular, if E(X) > 0 and by setting t = E(X), we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The standard second moment method is based on Chebyshev's inequality. It consists in showing that, for a given sequence of non-negative, integer-valued random variables ([X.sub.n]), Var([X.sub.n])/E2([X.sub.n]) tends to 0 as n [right arrow] [infinity], and thus concluding that [X.sub.n] > 0 a.a.s.

Markov's inequality states that, if X > 0 and t > 0, then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

In particular, if X|, [X.sub.2],... , [X.sub.n] are non-negative, integer-valued random variables, then E([X.sub.n]) [right arrow] 0 as nn[infinity] implies P[[X.sub.n] = 0] [right arrow] 1.

The following result is a variant of the so called method of moments. Let X be a random variable with a distribution that is determined by its moments (see [JLR00], p. 140, for a definition). If X|, [X.sub.2],... , [X.sub.n] are random variables with finite moments (E(|X|r) < 00, r > 1) such that E([X.sub.n])r [right arrow] E(X)r as n - [infinity] for every integer r > 1, then [X.sub.n] [right arrow] X. An example of distribution which is determined by its moments is the Poisson distribution.

We will use the following asymptotic notation. Let {an} and {bn} be two sequences of real numbers. For simplicity we assume that [a.sub.n],[b.sub.n ]> 0.

* an = O([b.sub.n]) if there exist constants no [member of] N and C > 0 such that an [less than or equal to] Cbn for n [less than or equal to] no.

* an = o([b.sub.n]) and an << [b.sub.n] mean an/[b.sub.n] [right arrow] 0 as n [right arrow] [infinity].

* an ~ [b.sub.n] if an/[b.sub.n] [right arrow] 1 as n [right arrow] [infinity].

4.1 Threshold for small tropical subgraphs

Let G be a fixed graph with vG vertices and eG edges. We denote by a = |Aut(G)| the cardinality of the automorphism group of G. One of the first problems studied by Erdos and Renyi in [ER60] was that of the existence of at least one copy of G in G(n,p). They determined the threshold function for that property in the special case in which G is a balanced graph (see below for the definition). Later in [Bol81] Bollobas extended this result to any arbitrary fixed graph. Formally, the threshold function for the property of containing a copy of G is n~1/[rho](G) where [rho](G) is the ratio of the number of edges to the number of vertices in the densest subgraph of G, that is,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where vH and eH stand for the number of vertices and edges of H, respectively.

The next theorem follows from the result of Bollobas and shows that the above threshold also holds for the property of the existence of a tropical copy of a given graph in G(n,p, c). In what follows, we will denote by [X.sub.n] = [X.sub.n] (G) the number of tropical copies of G in G(n, p, c). That is,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where the sum is over all copies G' of G, and

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Theorem 4.1. Let G be a fixed graph with at least one edge, eG > 0. Let c = [v.sub.G] = |V(G)|. Then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Proof: The theorem clearly holds if [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] show that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] The second moment of [X.sub.n] is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

As c is fixed, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

So, to complete the proof it suffices to show that E2/E2([X.sub.n]) = o(1). Since P[G', G" are tropical ] [greater than or equal to] c!/[c.sup.c] it follows that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Let [Y.sub.n] denote the number of copies of G in G(n,p). By splitting E([MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]) into two parts in the same way as for E([MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]), we obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Thus, as cis fixed and Var([Y.sub.n])/E2([Y.sub.n]) = o(1), it follows that E2/E2(Xn) = o(1), which completes the proof. []

In the next theorem we investigate the case in which pn1/[rho](G) [right arrow] [theta] as n [right arrow] [infinity], where [theta] is a positive constant. We are specially interested in a family of graphs called strictly balanced graphs defined as follows. A graph G is balanced if [rho](G) = eG/vG, that is, if eH/vH [less than or equal to] eG/vG for every H C G. G is strictly balanced if eH/vH < eG/vG whenever H [[subset].bar] G, that is to say that every proper subgraph of G is strictly less dense than the graph itself. Trees, cycles and complete graphs are strictly balanced.

Theorem 4.2. Let G be a fixed strictly balanced graph with v vertices and e edges. Denote by a = |Aut(G)| the number of elements of the automorphism group of G. Let [theta] be a positive constant and set p = [theta]/ Let Xn denote the number of tropical copies of G in G(n,p, c) with c = v. Then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where V([lambda]) is the Poisson distribution with mean [lambda].

Proof: The proof uses the method of moments described above. The expectation of Xn is easily estimated as follows.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

It is not hard to see that, for r > 2, the r-th factorial moment of Xn is equal to the expected number of ordered r-tuples (G1,... , Gr) of tropical copies of G in G(n,p, c), that is,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

We split E(Xn)r into two parts

E(Xn)r = E'r + E".

E'r is the expected number of ordered r-tuples of mutually vertex disjoint copies of G, while E" takes into consideration the other cases. We have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Since c is fixed, it follows that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where X is a random variable with Poisson distribution V([lambda]).

To complete the proof, it remains to show that E'r' [right arrow] 0 as n [right arrow] [infinity]. Clearly,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

It is shown in [JLR00], p. 67, that the right-hand side of the above inequality tends to 0 as n [right arrow] oo, which completes the proof. []

4.2 Complete tropical subgraphs

One of the most interesting results in the study of random graphs was discovered by Matula [Mat76] who proved that the clique number cl(G(n,p)) of G(n,p) is asymptotically almost surely concentrated on two consecutive values. This result was also found independently by Bollobas and Erdo"s [BE76]. Let 0 < p < 1 be fixed and set b = 1/p. Let the function f(n) be defined by

f(n) = 2 logb n - 2 logb logb n + 1 + 2 logb (e/2) .

Then, for any e > 0, the clique number of G(n,p) satisfies

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

This leads us to the natural question of what is the maximum number of colors c = c(n) which a.a.s. guarantees the existence of a tropical clique of order r in G(n,p, r), for every r [less than or equal to] c(n). The answer to this question is given by the following theorem. In particular, it is shown that c(n) differs from f(n) by an additive constant (not depending on n).

Theorem 4.3. Let 0 < p < 1 be fixed. Let c = c(n) be the function defined by

c(n) = 2 logb n - 2 logb logb n - 2 logb 2+1,

where b = 1/p. Then, for any e > 0, the following assertions hold.

(i) Ifr > [c(n) + e], then a.a.s. there is no complete tropical subgraph of order r in G(n, p, r).

(ii) If r [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] then a.a.s. G(n,p, r) contains a complete tropical subgraph of order r.

Proof: The proof is based on the first and second moment methods. Let [X.sub.r] be the random variable counting the number of tropical cliques of order r in G(n, p, r). The expectation of [X.sub.r] is given by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (1)

Using Stirling's formula, we get

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where b = 1/p. We observe that E([X.sub.r]) changes rapidly from [omega](1) to o(1) for values of r equivalent to 2 [log.sub.b] n. Indeed, let e > 0 be fixed, and set

c(n) = 2 [log.sub.b] n - 2 [log.sub.b] [log.sub.b] n - 2 [log.sub.b] 2 + 1.

If r > Lc(n) + [member of], then, as r is an integer, we have r > c(n) + e. Using this lower bound, and replacing r by (1 - o(1))2[log.sub.b]n in [log.sub.b]r of the above expression of E([X.sub.r]), we obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]#

Thus, by Markov's inequality, assertion (i) is proved.

Assume now that r is sufficiently large (r [right arrow]* [infinity]) and r < |_c(n) - ] . By a similar argument, we get

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (2)

Thus, assertion (ii) will hold, if for every r [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] In what follows, we assume that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] can be done in the same way. First, we need to estimate [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] be two subsets of vertices each of order r and having i vertices in common. Clearly,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Thus,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (3)

Relations (1) and (3) imply

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and

with

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

We estimate [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] as follows.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

To complete the proof, we need to show that, for [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] [right arrow] 0. Let us consider the bottom term (i = 2) in the sum for bn. We have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Let t := [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

It follows that, for sufficiently large n, the function g(i) is decreasing. Thus

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Now we consider the second part of the sum for bn. We have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

By setting j = r - i and interchanging the order of summation, we get

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Since by assumption [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], we have, for n large enough,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Therefore

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Since, by [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] it follows that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The proof is complete. []

4.3 Tropical tree components

Let G(n, p) be the random graph on n vertices with p = [theta] /n, where [theta] is a positive constant. Erdo"s and Renyi discovered in their original work [ER60] that the structure of G(n,p) undergoes sudden changes around p = 1/n. Roughly speaking, if [theta] < 1 then G(n,p) consists of small components, the largest of which is of order O(log n). While for [theta] > 1 many of the small components join together to form a giant component of order O(n). The remaining vertices are still in small components of order at most O (log n). This phenomenon is called the double jump, also known as the phase transition phenomenon. In the next theorem, we estimate the order of the largest tropical tree component in G(n, p, c) at the subcritical phase ([theta] < 1).

In what follows, we denote by T. the number of components of G(n,p, k) that are tropical trees of order k.

Theorem 4.4. Let p = [theta] /n, where 0 < [theta] < 1 is fixed. Let e G (0,1) be fixed. Set k = k(n, [theta], e) = [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] Then, asymptotically almost surely G(n,p, k) has a tropical component of order k [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] which is a tree.

Proof: Using Cayley's formula for the number kk 2 of labeled trees of order k, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Since p = [theta] /n = o(1) and k = O(logn), we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Therefore,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Thus, for [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] we have E(Tk) = -[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. To complete the proof, we need to compute the variance of [T.sub.k]. Clearly,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Consequently,

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Since [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] as n tends to infinity, and by Chebyshev inequality, it follows that P[Tk = 0] [less than or equal to] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], which completes the proof. []

In the next theorem, convergence in distribution of [T.sub.k] is established for certain values of k. The proof is based on the following special case of the method of moments (see [Bol01], p. 25). Let [lambda] = [lambda](n) be a non-negative bounded function on N. Let [X.sub.1],... , [X.sub.n] be non-negative integer-valued random variables such that, for every r = 1,2,... , E(X )r [right arrow][lambda]r as n [right arrow] ->. Then [X.sub.n] [right arrow] P([lambda]).

Theorem 4.5. Let p = [theta] /n, where 0 < [theta] < 1 is fixed. Let

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Denote by [T.sub.k] the number of components of G(n,p, k) that are tropical trees of order k. Then [T.sub.k] has asymptotically Poisson distribution P([lambda]) with mean

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

Proof: Note first that by a judicious choice of l, k is an integer. From the proof of Theorem 4.4, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

It is easily checked that E([T.sub.k]) is asymptotically equivalent to [lambda]. Since by assumption l = O(1) and [theta] is fixed, [lambda] is bounded. For every integer r > 2, the r-th factorial moment of [T.sub.k] is estimated as follows.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

The result follows from the method of moments previously mentioned. []

References
[ALN11]    S. Akbari, V. Liaghat, and A. Nikzad. Colorful paths in
           vertex-colorings of graphs. Electronic
           Journal of Combinatorics, 18:P17, 2011.
[AMK+]     J.-A. Angles d'Auriac, A. El Maftouhi, M. Karpinski, Y.
           Manoussakis, L. Montero,
           N. Narayanan, L. Rosaz, and J. Thapper. Tropical dominating
           sets in vertex-colored graphs.
           Unpublished results, submitted.
[BE76]     B. Bollobas and P. Erdo"s. Cliques in random graphs. In
           Mathematical Proceedings of the
           Cambridge Philosophical Society, volume 80, 1976.
[BHK+12]   S. Bruckner, F. Huffner, C. Komusiewicz, R. Niedermeier, S.
           Thiel, and J. Uhlmann. Partitioning
           into colorful components by minimum edge deletions. In
           Combinatorial Pattern
           Matching, pages 56-69, 2012.
[BHKN13]   S. Bruckner, F. Huffner, C. Komusiewicz, and R. Niedermeier.
           Evaluation of ilp-based approaches
           for partitioning into colorful components. In Software
           Engineering and Applications,
           pages 176-187, 2013.
[Bol81]    B. Bollobas. Threshold functions for small subgraphs. In
           Mathematical Proceedings of the
           Cambridge Philosophical Society, volume 90, 1981.
[Bol01]    B. Bollobas. Random Graphs - Second Edition. Cambridge
           University Press, 2001.
[CPM10]    Eduardo Corel, Florian Pitschi, and Burkhard Morgenstern. A
           min-cut algorithm for the
           consistency problem in multiple sequence alignment.
           Bioinformatics, 26:1015-1021, 2010.
[ER60]     P. Erdo"s and A. Renyi. On the evolution of random graphs.
           Publications of the Mathematical
           Institute of the Hungarian Academy of Sciences, 5:17-61,
           1960.
[FFHV 11]  M. Fellows, G. Fertin, D. Hermelin, and S. Vialette. Upper
           and lower bounds for finding
           connected motifs in vertex-colored graphs. J. Comput. Syst.
           Sci., 77(4):799-811, 2011.
[FHH+]     F. Foucaud, A. Harutyunyan, P. Hell, S. Legay, Y.
           Manoussakis, and R. Naserasr. Tropical
           homomorphisms in vertex-coloured graphs. Unpublished
           results.
[JLR00]    S. Janson, T. Luczak, and A. Rucinski. Random Graphs.
           Wiley-Interscience Series in Discrete
           Mathematics and Optimization. Wiley, 2000.
[Li01]     A. Li. A generalization of the gallai-roy theorem. Graphs
           and Combinatorics, 17:681-685,
           2001.
[Lin07]    C. Lin. Simple proofs of results on paths representing all
           colors in proper vertex-colorings.
           Graphs andCombinatorics, 23:201-203, 2007.
[Mat76]    D. W. Matula. The largest clique size in a random graph.
           Technical Report, Dept. of Computer
           Science, Southern Methodist University Dallas, 1976.
[PA]       A. Popa and A. Adamaszek. Algorithmic and hardness results
           for the colorful components
           problems. In press, to appear in LATIN 2014.
[ZSLS11]   C. Zheng, K. Swenson, E. Lyons, and D. Sankoff. Omg!
           orthologs in multiple genomes
           - competing graph-theoretical formulations. In Workshop on
           Algorithms in Bioinformatics,
           pages 364-375, 2011.


Email addresses: jagw40k@free.fr (J.-A. Angle`s d'Auriac), nathann.cohen@gmail.com (N. Cohen), hakim.maftouhi@orange.fr (A. El Maftouhi), ararat.harutyunyan@math.univ-toulouse.fr (A. Harutyunyan), legay@lri.fr (S. Legay), yannis@lri.fr (Y. Manoussakis)

Jean-Alexandre Angles d'Auriac (1) Nathann Cohen (1)

Hakim El Maftouhi (1) Ararat Harutyunyan (2*)

Sylvain Legay (1) Yannis Manoussakis (1)

(1) L.R.I., Universite Paris-Sud, France.

(2) Mathematical Institute, University of Toulouse III (Paul Sabatier), France.

received 2nd Feb. 2015, revised 14th July 2016, accepted 26th July 2016.

(*) Research supported by an FQRNT fellowship and a Digiteo postdoctoral scholarship, the latter when the author was at Universite Paris-Sud.
COPYRIGHT 2016 DMTCS
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2016 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:d'Auriac, Jean-Alexandre Angles; Cohen, Nathann; Maftouhi, Hakim El; Harutyunyan, Ararat; Legay, Syl
Publication:DMTCS Proceedings
Article Type:Report
Date:Jan 1, 2016
Words:9652
Previous Article:An extremal problem for a graphic sequence to have a realization containing every 2-tree with prescribed size.
Next Article:Linear recognition of generalized Fibonacci cubes [Q.sub.h](111).
Topics:

Terms of use | Privacy policy | Copyright © 2019 Farlex, Inc. | Feedback | For webmasters