scientific article; zbMATH DE number 398961

From MaRDI portal
Publication:4201576





Let \(G=(V,E)\) be a simple graph with \(| V|=n\). A connected graph without cut vertices is called a block. The closure \(c(G)\) of \(G\) is a graph which can be obtained from \(G\) by recursively joining pairs of nonadjacent vertices whose degree sum is at least \(n\) until no such pair remains. In this paper nonadjacency relations in \(c(G)\) of any two vertices are investigated which are nonadjacent in \(G\) and which are not cut vertices. The author obtains the following results: Theorem 2.1. Let \(z\) be a cut vertex which separates \(E\) into two nonempty subsets \(E_ 1\) and \(E_ 2\) and let \(G_ i\) be the subgraph of \(G\) with \(E(G_ i)=E_ i\), \(i=1,2\). Then any two vertices \(x\) and \(y\) with \(x\in V(G_ 1)\), \(y\in V(G_ 2)\), \(x\neq z\), \(y\neq z\) are nonadjacent vertices of \(c(G)\). Theorem 2.3. If \(K\) is a maximal block of \(G\), then for any two vertices \(x\), \(y\) which are nonadjacent in \(G\): (a) If \(| V(K)|\leq{1\over 2}(n+3)\) and \(x\) and \(y\) are not cut vertices, then \(x\) is not adjacent to \(y\) in \(c(G)\). (b) If \(x,y\notin V(K)\), then \(x\) is not adjacent to \(y\) in \(c(G)\). Finally it is shown that in the case of many cut vertices and large blocks the implementation time of the known algorithm of Samir Khuller to find \(c(G)\) can be improved. If \(G\) has \(p\geq 1\) cut vertices and \(| V(K)|\leq{1\over 2}(n+3)\) for each block \(K\) of \(G\), then the algorithm runs on \(O(pn^ 2)\) time.











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4201576)