|
This article is cited in 2 scientific papers (total in 2 papers)
Algorithms for computing the multiclique degree and the biclique degreeof a series-parallel graph
V. V. Lepin Belarusian State University
Abstract:
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.
Received: 30.05.2010
Citation:
V. V. Lepin, “Algorithms for computing the multiclique degree and the biclique degreeof a series-parallel graph”, Tr. Inst. Mat., 18:2 (2010), 60–78
Linking options:
https://www.mathnet.ru/eng/timb18 https://www.mathnet.ru/eng/timb/v18/i2/p60
|
|