Algorithms for computing the multiclique degree and the biclique degreeof a series-parallel graph

V. V. Lepin

Trudy Instituta matematiki, Tome 18 (2010) no. 2, pp. 60-78

Résumé

A multiclique is a complete multipartite subgraph of a graph. A biclique is a complete bipartite subgraph of a graph. A multiclique cover of a graph $G$ is a collection of multicliques of $G$ whose edge sets cover the edge set of $G$ (every edge of $G$ belongs to at least one multiclique of the collection). Given a multiclique cover $\mathcal{C}$ of $G$ and a vertex $v\in V(G),$ the degree $v$ on $\mathcal{C}$ is $\rho(G,\mathcal{C},v)=|\{H\in\mathcal{C}:v\in H\}|$. The degree of a multiclique cover $\mathcal{C}$ of $G$, denoted by $\rho(G,\mathcal{C})$, is defined to be: $\rho(G,\mathcal{C})=\max\limits_{v\in V(G)}\rho(G,\mathcal{C},v)$. The multiclique degree of $G$, denoted by $\rho(G)$, is the minimum value of $\rho(G,\mathcal{C})$ as $\mathcal{C}$ ranges over all coverings of $G$. Polinomial-time algorithms for computing the multiclique degree and the biclique degree of a (simple) series-parallel graph are given.