Sousa, Teresa. "
Friendship Decompositions of Graphs: The general problem."
Open Journal of Applied Sciences. Vol. 2. No. 4B (2012): 30-33.
AbstractA friendship graph is a graph consisting of cliques sharing a common vertex. In this paper we investigate the maximum number of elements in an optimal friendship decomposition of graphs of order n. We obtain upper and lower bounds for this number. These bounds relate this problem with the classical Ramsey numbers.
Sousa, Teresa. "
The H-Decomposition Problem for Graphs."
Applied Mathematics. 3.11 (2012): 1719-1722.
AbstractThe concept of H-decompositions of graphs was first introduced by Erdös, Goodman and Pósa in 1966, who were motivated by the problem of representing graphs by set intersections. Given graphs G and H, an H-decomposition of G is a partition of the edge set of G such that each part is either a single edge or forms a graph isomorphic to H. Let Ф(n,H) be the smallest number Ф, such that, any graph of order n admits an H-decomposition with at most Ф parts. The exact computation of Ф(n,H) for an arbitrary H is still an open problem. Recently, a few papers have been published about this problem. In this survey we will bring together all the results about H-decompositions. We will also introduce two new related problems, namely Weighted H-Decompositions of graphs and Monochromatic H-Decompositions of graphs.
Sousa, Teresa. "
H-decompositions of r-graphs when H is an r-graph with exactly 2 edges."
Electronic Journal of Combinatorics. 17 (2010): Research Paper 40, 8.
Abstract"Given two r-graphs G and H, an H-decomposition of G is a partition of the edge set of G such that each part either is a single edge or forms a graph isomorphic to H. The minimum number of parts in an H-decomposition of G is denoted by φrH(G). By a 2-edge-decomposition of an r-graph we mean an H-decomposition for any fixed r-graph H with exactly 2 edges. In the special cases where the two edges of H intersect in exactly 1, 2 or r−1 vertices, these 2-edge-decompositions will be called bowtie, domino and kite, respectively. The value of the function φrH(n) will be obtained for bowtie, domino and kite decompositions of r-graphs.''
Sousa, Teresa. "
Minimum Weight H-Decompositions of Graphs: The Bipartite Case."
Electronic Journal of Combinatorics. 18(1) (2011): P126, 10 pp.
AbstractGiven graphs G and H and a positive number b, a weighted (H,b)-decomposition of G is a partition of the edge set of G such that each part is either a single edge or forms an H-subgraph. We assign a weight of b to each H-subgraph in the decomposition and a weight of 1 to single edges. The total weight of the decomposition is the sum of the weights of all elements in the decomposition. Let f(n,H,b) be the the smallest number such that any graph G of order n admits an (H,b)-decomposition with weight at most f(n,H,b). The value of the function f(n,H,b) when b=1 was determined, for large n, by Pikhurko and Sousa [Pikhurko, O. and Sousa, T., Minimum H-Decompositions of Graphs, Journal of Combinatorial Theory, B, 97 (2007), 1041--1055.Here we determine the asymptotic value of f(n,H,b)for any fixed bipartite graph H and any value of b as n tends to infinity.
Liu, H., Â. Mestre, and Teresa Sousa. "
Rainbow vertex k-connection in graphs."
Discrete Applied Mathematics. 161.16-17 (2013): 2549-2555.
AbstractLet k be a positive integer and G be a k-connected graph. An edge-coloured path is rainbow if its edges have distinct colours. The rainbow k-connection number of G, denoted by rc_k(G), is the minimum number of colours required to colour the edges of G so that any two vertices of G are connected by k internally vertex-disjoint rainbow paths. The function rc_k(G) was first introduced by Chartrand, Johns, McKeon, and Zhang in 2009, and has since attracted considerable interest. In this paper, we consider a version of the function rc_k(G) which involves vertex-colourings. A vertex-coloured path is vertex-rainbow if its internal vertices have distinct colours. The rainbow vertex k-connection number of G, denoted by rvc_k(G), is the minimum number of colours required to colour the vertices of G so that any two vertices of G are connected by k internally vertex-disjoint vertex-rainbow paths. We shall study the function rvc_k(G) when G is a cycle, a wheel, and a complete multipartite graph. We also construct graphs G where rc_k(G) is much larger than rvc_k(G) and vice versa so that we cannot in general bound one of rc_k(G) and rvc_k(G) in terms of the other.