Friendship decompositions of graphs
- Citation:
- Sousa, Teresa. "Friendship decompositions of graphs." Discrete Mathemathics. 308 (2008): 3352-3360.
Abstract:
Let G be a simple graph. A clique is a subgraph of G isomorphic to a complete graph, and a t-friendship graph is a graph consisting of t edge-disjoint cliques sharing one vertex. A t-friendship decomposition of G for a fixed value of t is a set F of edge-disjoint t-friendship subgraphs of G such that every edge of G belongs to exactly one element of F. It is proved that any graph of order n admits a t-friendship decomposition with at most n2/4t+n/4t+n elements for all fixed t≥2. For t=2,3 exact bounds are given. For t=2 the bound is ⌈n2/8⌉ for n even and (n2−1)/8 for n odd; for t=3 the bound is ⌈n2/12⌉ for n even and ⌈(n2−1)/12⌉ for n odd.
