Search

In this paper we find the trace-minimal graph in the class of (v+1)-regular graphs with 2v vertices. It is proved that the join of an empty graph on v-1 vertices and a cycle graph on v+1 vertices is the unique trace-minimal graph in this class. These findings have applications to experimental designs in statistics, and to the geometry of the unit hypercube in higher dimensions. We present these applications.

We consider the minimum number of cliques needed to partition the edge set of D(G), the distance multigraph of a simple graph G. Equivalently, we seek to minimize the number of elements needed to label the vertices of a simple graph G by sets so that the distance between two vertices equals the cardinality of the intersection of their labels. We use a fractional analogue of this parameter to find lower bounds for the distance multigraphs of various classes of graphs. Some of the bounds are shown to be exact.

A k-digraph is an orientation of a multi-graph that is without loops and contains at most k edges between any pair of distinct vertices. So 1-digraph is an oriented graph, and complete 1-digraph is a tournament. We obtain necessary and sufficient conditions for a sequence of non-negative integers in non-decreasing order to be a sequence of numbers, called marks, attached to vertices of 2-digraph.

Let G = (V, E) be an undirected simple graph with u e V. If there exist any two vertices in G whose distance becomes longer when a vertex u is removed, then u is defined as a hinge vertex. Finding the set of hinge vertices in a graph is useful for identifying critical nodes in an actual network. A number of studies concerning hinge vertices have been made in recent years. In a number of graph problems, it is known that more efficient sequential or parallel algorithms can be developed by restricting classes of graphs. In this paper, we shall propose a parallel algorithm which runs in O(log n) time with O(n/log n) processors on EREW PRAM for finding all hinge vertices of a circular-arc graph.

We consider a conditionally Poisson random-graph model in which the mean degrees, ``capacities,'' follow a power-tail distribution with finite mean and infinite variance. Such a graph of size $N$ has a giant component that is supersmall in the sense that the typical distance between vertices is of order $\log\log N$. The shortest paths travel through a core consisting of nodes with high mean degrees. In this paper we derive upper bounds for the distance between two random vertices when an upper part of the core is removed, including the case that the whole core is removed.

Let $D^d_n$ denote the $d$-dimensional grid with diagonals, that is, the graph with vertex set $\{1,2,\ldots,n\}^d$ and with edges connecting every two vertices that differ by at most $1$ in every coordinate. We prove that for an arbitrary coloring of the vertices of $D^d_n$ by two colors there exists a monochromatic connected subgraph with at least $n^{d-1}-d^2n^{d-2}$ vertices; and thus the “horizontal layer” coloring (by the parity of the first coordinate) is almost optimal. We also consider a $d$-dimensional triangulated grid; this is the graph ($1$-skeleton) of a triangulation of the solid cube $[1,n]^d$ that refines the subdivision of $[1,n]^d$ into the grid of unit cubes. Here every two-coloring has a monochromatic connected subgraph with $\Omega(n^{d-1}/\sqrt d)$ vertices. These results are proved by combining combinatorial and topological arguments with suitable isoperimetric inequalities, and they can be viewed as $d$-dimensional generalizations of the planar HEX lemma.

Weighted peripheral graph Gd of a graph G has the peripheral vertices of G as its vertices and the diametral paths between the peripheral vertices of G as its edges. The structural properties of this weighted graph for some classes of graphs are discussed and bounds of certain parameters are identified. For the C# program developed to determine the parameters involved in the study, corresponding output for a sample graph is also presented. Remote nodes, high priority routes between them and strategic location problems of real life networks are some areas where these results can be applied.

For a set S of vertices and the vertex v in a connected graph G, $$\displaystyle \max _{x \in S}dx,v$$ is called the S-eccentricity of v in G. The set of vertices with minimum S-eccentricity is called the S-center of G. Any set Aof vertices of G such that A is an S-center for some set S of vertices of G is called a center set. We identify the center sets of certain classes of graphs namely, Block graphs, $$K_{m,n}$$, $$K_n-e$$, wheel graphs, odd cycles and symmetric even graphs. A graph G is called center critical if there does not a exist proper subset S of the vertex set whose S-center is the center of the graph. Here we characterize this class of graphs.

Given a connected graph $G=(V,E)$, the closeness centrality of a vertex $v$ is defined as $\frac{n-1}{\sum_{w \in V} d(v,w)}$. This measure is widely used in the analysis of real-world complex networks, and the problem of selecting the $k$ most central vertices has been deeply analysed in the last decade. However, this problem is computationally not easy, especially for large networks: in the first part of the paper, we prove that it is not solvable in time $\O(|E|^{2-\epsilon})$ on directed graphs, for any constant $\epsilon>0$, under reasonable complexity assumptions. Furthermore, we propose a new algorithm for selecting the $k$ most central nodes in a graph: we experimentally show that this algorithm improves significantly both the textbook algorithm, which is based on computing the distance between all pairs of vertices, and the state of the art. For example, we are able to compute the top $k$ nodes in few dozens of seconds in real-world networks with millions of nodes and edges. Finally, as a case study, we compute the $10$ most central actors in the IMDB collaboration network, where two actors are linked if they played together in a movie, and in the Wikipedia citation network, which contains a directed edge from a page $p$ to a page $q$ if $p$ contains a link to $q$.

Let G be a graph and S be a subset of vertices of G. With I[S] we denote the set of all vertices on some geodesic (shortest path) between two vertices of S. A contour vertex of a graph is one whose eccentricity is at least as big as all its neighbors' eccentricities. Let C be the set of contour vertices of a graph. We provide the first example of a graph where I[I[C]] do not coincide with the vertex set of the graph.

In this paper, for the purpose of measuring the non-self-centrality extent of non-selfcentered graphs, a novel eccentricity-based invariant, named as non-self-centrality number (NSC number for short), of a graph G is defined as follows: \(N\left( G \right) = \sum\nolimits_{{v_i}{v_j} \in V\left( G \right)} {|{e_i} - {e_j}|} \) where the summation goes over all the unordered pairs of vertices in G and ei is the eccentricity of vertex vi in G, whereas the invariant will be called third Zagreb eccentricity index if the summation only goes over the adjacent vertex pairs of graph G. In this paper, we determine the lower and upper bounds on N(G) and characterize the corresponding graphs at which the lower and upper bounds are attained. Finally we propose some attractive research topics for this new invariant of graphs.

Given an undirected graph \(G = (V, E)\) with \(|V| = n\) and a vertex coloring, a vertex v is happy if v and all its neighbors have the same color. An edge is happy if its end vertices have the same color. Given a partial coloring of the vertices of the graph using k colors, the Maximum Happy Vertices (also called k-MHV) problem asks to color the remaining vertices such that the number of happy vertices is maximized. The Maximum Happy Edges (also called k-MHE) problem asks to color the remaining vertices such that the number of happy edges is maximized. For arbitrary graphs, k-MHV and k-MHE are NP-Hard for \(k \ge 3\). In this paper we study these problems for trees. For a fixed k we present linear time algorithms for both the problems. In general, for any k the proposed algorithms take \(O(nk \log k)\) and O(nk) time respectively.

We study the problem of deleting a minimum cost set of vertices from a given vertex-weighted graph in such a way that the resulting graph has no induced path on three vertices. This problem is often called cluster vertex deletion in the literature and admits a straightforward 3-approximation algorithm since it is a special case of the vertex cover problem on a 3-uniform hypergraph. Very recently, You et al.i¾ź[14] described an efficient 5/2-approximation algorithm for the unweighted version of the problem. Our main result is a 7/3-approximation algorithm for arbitrary weights, using the local ratio technique. We further conjecture that the problem admits a 2-approximation algorithm and give some support for the conjecture. This is in sharp constrast with the fact that the similar problem of deleting vertices to eliminate all triangles in a graph is known to be UGC-hard to approximate to within a ratio better than 3, as proved by Guruswami and Leei¾ź[7].

Let G(k, n) be the set of simple graphs (i.e. without multiple edges or loops) that have n vertices and the minimum degree of vertices is k. The Randic index of a graph G is: , where δu is the degree of vertex u and the summation extends over all edges (uv) of G. Using linear programming, we find the extremal graphs or give good bounds for this index when the number nk of vertices of degree kis n−k+t, for 0tk and kn/2. We also prove that for nkn−k, (kn/2) the minimum value of the Randic index is attained for the graph .

We report some properties of the largest eigenvalue Lambda(1) of the distance matrix of a connected graph, in particular, the upper and lower bounds for Lambda(1) involving the sum of the squares of the distances between all unordered pairs of vertices and the sum of the distances between a given vertex and all other vertices. We also give the relationship between Lambda(1) and the first Zagreb index and the Wiener index. Additionally, we give the Nordhaus-Gaddum-type result for Lambda(1).

It is proved that, if n is sufficiently large compared with d, then the smallest number of edges in a 2-connected graph with n vertices and diameter at most d is exactly ⌈(dn-2d-1)/(d-1)⌉.

In this article, we consider the following problem: Of all trees on n vertices with diameter d (both fixed) which tree achieves the maximal Laplacian spectral radius? We show that the maximal Laplacian spectral radius is obtained uniquely at , where is a tree obtained by taking a path P on d + 1 vertices and adding n-d-1 pendant vertices to a center point of P.

A shortest path connecting two vertices u and v is called a u-v geodesic. The distance between u and v in a graph G, denoted by d"G(u,v), is the number of edges in a u-v geodesic. A graph G with n vertices is panconnected if, for each pair of vertices u,[email protected]?V(G) and for each integer k with d"G(u,v)=

Consider a tree Pn-g,g , n≥ 2, 1≤ g≤ n-1 on n vertices which is obtained from a path on [1,2, … ,n-g] vertices by adding g pendant vertices to the pendant vertex n-g. We prove that over all trees on n ≥ 5 vertices, the distance between center and characteristic set, centroid and characteristic set, and center and centroid is maximized by trees of the form Pn-g,g , 2 ≤ g ≤ n-3. For n≥ 5, we also supply the precise location of the characteristic set of the tree Pn-g,g , 2 ≤ g ≤ n-3.

A set of vertices S in a graph G is a routing set if it ensures some kind of connectivity between all pairs of vertices outside of S. Additional constraints may apply; a connected dominating set, for instance, is a special case of a routing set. We determine the size of a minimum routing set in subgraphs of the integer lattice, as well as (asymptotically) for the lattice itself.

Given a graph G with n vertices, we call ck(G) the minimum number of elementary cycles of length at most k necessary to cover the vertices of G. We bound ck(G) from the minimum degree and the order of the graph.

We prove that every 2-connected outerplanar graph of order at least k (k>=3) contains a path on k vertices with all vertices of degree at most k+3 and a path on k vertices with degree sum at most 4k-2. Further, every 2-connected outerplanar graph without adjacent vertices with degree sum =

A set S of vertices in a graph G is called a paired-dominating set if it dominates V and 〈S〉 contains at least one perfect matching. We characterize the set of vertices of a tree that are contained in all minimum paired-dominating sets of the tree.

Shortest path problems can be solved very efficiently when a directed graph is nearly acyclic. Earlier results defined a graph decomposition, now called the 1-dominator set, which consists of a unique collection of acyclic structures with each single acyclic structure dominated by a single associated trigger vertex. In this framework, a specialised shortest path algorithm only spends delete-min operations on trigger vertices, thereby making the computation of shortest paths through non-trigger vertices easier. A previously presented algorithm computed the 1-dominator set in O(mn) worst-case time, which allowed it to be integrated as part of an O(mn+nrlogr) time all-pairs algorithm. Here m and n respectively denote the number of edges and vertices in the graph, while r denotes the number of trigger vertices. A new algorithm presented in this paper computes the 1-dominator set in just O(m) time. This can be integrated as part of the O(m+rlogr) time spent solving single-source, improving on the value of r obtained by the earlier tree-decomposition single-source algorithm. In addition, a new bidirectional form of 1-dominator set is presented, which further improves the value of r by defining acyclic structures in both directions over edges in the graph. The bidirectional 1-dominator set can similarly be computed in O(m) time and included as part of the O(m+rlogr) time spent computing single-source. This paper also presents a new all-pairs algorithm under the more general framework where r is defined as the size of any predetermined feedback vertex set of the graph, improving the previous all-pairs time complexity from O(mn+nr2) to O(mn+r3).

Consider a connected undirected graph G=(V,E), a subset of vertices [email protected]?V, and an integer r>=1; for any vertex [email protected]?V, let B"r(v) denote the ball of radius r centred at v, i.e., the set of all vertices linked to v by a path of at most r edges. If for all vertices [email protected]?V (respectively, [email protected][email protected]?C), the sets B"r(v)@?C are all nonempty and different, then we call C an r-identifying code (respectively, an r-locating-dominating code). We study the extremal values of the cardinality of a minimum r-identifying or r-locating-dominating code in any connected undirected graph G having a given number, n, of vertices. It is known that a minimum r-identifying code contains at least @?log"2(n+1)@? vertices; we establish in particular that such a code contains at mostn-1 vertices, and we prove that these two bounds are reached. The same type of results are given for locating-dominating codes.

International audience; Let G=(V,E) be a graph. A k-neighborhood in G is a set of vertices consisting of all the vertices at distance at most k from some vertex of G. The hypergraph on vertex set V whose edge set consists of all the k-neighborhoods of G for all k is the neighborhood hypergraph of G. Our goal in this paper is to investigate the complexity of a graph in terms of its neighborhoods. Precisely, we define the distance VC-dimension of a graph G as the maximum taken over all induced subgraphs G′ of G of the VC-dimension of the neighborhood hypergraph of G′. For a class of graphs, having bounded distance VC-dimension both generalizes minor closed classes and graphs with bounded clique-width.Our motivation is a result of Chepoi et al. (2007) asserting that every planar graph of diameter 2ℓ can be covered by a bounded number of balls of radius ℓ. In fact, they obtained the existence of a function f such that every set F of balls of radius ℓ in a planar graph admits a hitting set of size f(ν) where ν is the maximum number of pairwise disjoint elements of F.Our goal is to generalize the proof of Chepoi et al. (2007) with the unique assumption of bounded distance VC-dimension of neighborhoods. In other words, the set of balls of fixed radius in a graph with bounded distance VC-dimension has the Erdős–Pósa property.

Recently a new graph convexity was introduced, arising from Steiner intervals in graphs that are a natural generalization of geodesic intervals. The Steiner tree of a set $W$ on $k$ vertices in a connected graph $G$ is a tree with the smallest number of edges in $G$ that contains all vertices of $W$. The Steiner interval $I(W)$ of $W$ consists of all vertices in $G$ that lie on some Steiner tree with respect to $W$. Moreover, a set $S$ of vertices in a graph $G$ is $k$-Steiner convex, denoted $g_k$-convex, if the Steiner interval $I(W)$ of every set $W$ on $k$ vertices is contained in $S$. In this paper we consider two types of local convexities. In particular, for every $k \gt 3$, we characterize graphs with $g_k$-convex closed neighborhoods around all vertices of the graph. Then we follow with a characterization of graphs with $g_4$-convex closed neighborhoods around all $g_4$-convex sets of the graph.

We study the sizes of connected components according to their excesses during a random graph process built with n vertices. The considered model is the continuous one defined in [17]. An l-component is a connected component with l edges more than vertices. l is also called the excess of such a component. As our main result, we show that when l and n/l are both large, the expected number of vertices that ever belong to an l-component is about 121/3 l1/3 n2/3. We also obtain limit theorems for the number of creations of l-components.

It is shown that for every e>0 there exists a constant L such that every triangle-free graph on n vertices with minimum degree at least (1/3+e)n is homomorphic to a triangle-free graph on at most L vertices.

An L(2, 1)-labeling of a graph is an assignment of nonnegative integers to its vertices so that adjacent vertices get labels at least two apart and vertices at distance two get distinct labels. The λ-number of a graph G, denoted by λ(G), is the minimum range of labels taken over all of its L(2, 1)-labelings. We show that the λ-number of the Cartesian product of any two cycles is 6, 7 or 8. In addition, we provide complete characterizations for the products of two cycles with λ-number exactly equal to each one of these values.

Given a graph G = (V,E), a set of vertices S ⊆ V covers ν ∈ V if the edge connectivity between S and ν is at least a given number k. Vertices in S are called sources. The source location problem is a problem of finding a minimum-size source set covering all vertices of a given graph. This paper presents a new variation of the problem, called maximum-cover source-location problem, which finds a source set S with a given size p, maximizing the sum of the weight of vertices covered by S. It presents an O(np + m + n log n)-time algorithm for k = 2, where n = |V| and m = |E|. Especially it runs linear time if G is connected. This algorithm uses a subroutine for finding a subtree with the maximum weight among p-leaf trees of a given vertex-weighted tree. For the problem we give a greedy-based linear-time algorithm, which is an extension of the linear-time algorithm for finding a longest path of a given tree presented by E. W. Dijkstra around 1960. Moreover, we show some polynomial solvable cases, e.g., a given graph is a tree or (k - 1)-edge-connected, and NP-hard cases, e.g., a vertex-cost function is given or G is a digraph.

For a set X of vertices of a graph fulfilling local connectedness conditions, the existence of a cycle containing X is proved.

The black and white traveling salesman problem (BWTSP) is defined on a graph G whose vertex set is partitioned into black and white vertices. The aim is to design a shortest Hamiltonian tour on G subject to cardinality and length constraints: both the number of white vertices as well as the length of the tour between two consecutive black vertices are bounded above. The BWTSP has applications in airline scheduling and in telecommunications. This paper proposes an integer linear formulation for the undirected BWTSP, as well as several classes of valid inequalities. An exact branch-and-cut algorithm is then developed. Extensive tests show that it can solve exactly instances involving up to 100 vertices. The algorithm can also be applied directly to solve unit demand vehicle routing problems of similar sizes.

The k-edge-connectivity augmentation problem for a specified set of vertices of a graph with degree constraints, kECA-SV-DC, is defined as follows: "Given an undirected multigraph G = (V, E), a specified set of vertices S ⊆ V and a function g: V→Z+∪{∞}, find a smallest set E' of edges such that (V, E ∪ E') has at least k edge-disjoint paths between any pair of vertices in S and such that, for any νe V, E' includes at most g(v) edges incident to v, where Z+ is the set of nonnegative integers." This paper first shows polynomial time solvability of kECA-SV-DC and then gives a linear time algorithm for 2ECA-SV-DC.

We consider parameterized problems where some separation property has to be achieved by deleting as few vertices as possible. The following five problems are studied: delete k vertices such that (a) each of the given ℓ terminals is separated from the others, (b) each of the given ℓ pairs of terminals is separated, (c) exactly ℓ vertices are cut away from the graph, (d) exactly ℓ connected vertices are cut away from the graph, (e) the graph is separated into at least ℓ components. We show that if both k and ℓ are parameters, then (a), (b) and (d) are fixed-parameter tractable, while (c) and (e) are W[1]-hard.

The 2-vertex-connectivity augmentation problem for a specified set of vertices of a graph with degree constraints, 2VCA-SV-DC, is defined as follows: "Given an undirected graph G = (V,E), a specified set of vertices S ⊆ V with |S| ≥ 3 and a function g : V → Z+ ∪ {∞}, find a smallest set E' of edges such that (V,E ∪ E') has at least two internally-disjoint paths between any pair of vertices in S and such that vertex-degree increase of each v ∈ V by the addition of E' to G is at most g(v), where Z+ is the set of nonnegative integers." This paper shows a linear time algorithm for 2VCA-SV-DC.

Let G be a finite simple connected graph. A vertex v is a boundary vertex of G if there exists a vertex u such that no neighbor of v is further away from u than v. We obtain a number of properties involving different types of boundary vertices: peripheral, contour and eccentric vertices. Before showing that one of the main results in [G. Chartrand, D. Erwin, G.L. Johns, P. Zhang, Boundary vertices in graphs, Discrete Math. 263 (2003) 25-34] does not hold for one of the cases, we establish a realization theorem that not only corrects the mentioned wrong statement but also improves it. Given [email protected]?V(G), its geodetic closure I[S] is the set of all vertices lying on some shortest path joining two vertices of S. We prove that the boundary vertex set @?(G) of any graph G is geodetic, that is, I[@?(G)]=V(G). A vertex v belongs to the contour Ct(G) of G if no neighbor of v has an eccentricity greater than v. We present some sufficient conditions to guarantee the geodeticity of either the contour Ct(G) or its geodetic closure I[Ct(G)].

Let G = (V, E) be a graph with n vertices and let P be a set of n points in the plane. We show that deciding whether there is a planar straight-line embedding of G such that the vertices V are embedded onto the points P is NP-complete, even when G is 2-connected and 2-outerplanar. This settles an open problem posed in [2, 4, 13].

Among all connected cactuses with n vertices we find a unique graph whose largest eigenvalue (index, for short) is maximal.

The natural metric of a weighted graph is the length of the shortest paths between all pairs of vertices. The investigated problem consists in a representation of a given metric by a graph, such that the total length of the graph is minimized. For that purpose, we give a constructive algorithm based on a technique of reduction, fusion and deletion. We then show some results on a set of various distance matrices whose optimal realization is known.

A set S of vertices in a graph G is a paired-dominating set of G if every vertex of G is adjacent to some vertex in S and if the subgraph induced by S contains a perfect matching. We characterize the set of vertices of a tree that are contained in all, or in no, minimum paired-dominating sets of the tree.

In this paper, we prove that every 3-connected claw-free graph on n vertices contain a cycle of length at least min { n , 6 δ − 17 } , hereby improving several known results.

This paper introduces the notion of informative labeling schemes for arbitrary graphs. Let f(W) be a function on subsets of vertices W. An f labeling scheme labels the vertices of a weighted graph G in such a way that f(W) can be inferred (or at least approximated) efficiently for any vertex subset W of G by merely inspecting the labels of the vertices of W, without having to use any additional information sources.A number of results illustrating this notion are presented in the paper. We begin by developing f labeling schemes for three functions f over the class of n-vertex trees. The first function, SepLevel, gives the separation level of any two vertices in the tree, namely, the depth of their least common ancestor. The second, LCA, provides the least common ancestor of any two vertices. The third, Center, yields the center of any three given vertices v1,v2,v3 in the tree, namely, the unique vertex z connected to them by three edge-disjoint paths. All of these three labeling schemes use O(log2n)-bit labels, which is shown to be asymptotically optimal.Our main results concern the function Steiner(W), defined for weighted graphs. For any vertex subset W in the weighted graph G, Steiner(W) represents the weight of the Steiner tree spanning the vertices of W in G. Considering the class of n-vertex trees with M-bit edge weights, it is shown that for this class there exists a Steiner labeling scheme using O((M+logn)logn) bit labels, which is asymptotically optimal. It is then shown that for the class of arbitrary n-vertex graphs with M-bit edge weights, there exists an approximate-Steiner labeling scheme, providing an estimate (up to a factor of O(logn)) for the Steiner weight Steiner(W) of a given set of vertices W, using O((M+logn)log2n) bit labels.

Let G=(V, E) be a graph with vertex set V of size n and edge set E of size m. A vertex v∈V is called a hinge vertex if there exist two vertices in V\{v} such that their distance becomes longer when v is removed. In this paper, we present a distributed algorithm that finds all hinge vertices on an arbitrary graph. The proposed algorithm works for named static asynchronous networks and achieves O(n 2) time complexity and O(m) message complexity. In particular, the total messages exchanged during the algorithm are at most 2m(log n+nlog n+1) bits.

An orthogonal drawing of a graph is an embedding of the graph in the rectangular grid, with vertices represented by axis-aligned boxes, and edges represented by paths in the grid that only possibly intersect at common endpoints. In this paper we study three-dimensional orthogonal drawings and provide lower bounds for three scenarios: (1) drawings where the vertices have a bounded aspect ratio, (2) drawings where the surfaces of vertices are proportional to their degrees, and (3) drawings without any such restrictions. Then we show that these lower bounds are asymptotically optimal, by providing constructions that in all scenarios match the lower bounds within a constant factor.

An L(2,1)-labeling of a graph is an assignment of nonnegative integers to its vertices so that adjacent vertices get labels at least two apart and vertices at distance two get distinct labels. A graph is said to be λ-critical if λ is the minimum span taken over all of its L(2,1)-labelings, and every proper subgraph has an L(2,1)-labeling with span strictly smaller than λ. Georges and Mauro have studied 5-critical trees with maximum degree Δ=3 by examining their path-like substructures. They also presented an infinite family of 5-critical trees of maximum degree Δ=3. We generalize these results for λ-critical trees with Δ⩾4.

This paper proves that for every positive integers n, k and any positive number e, we can explicitly construct a DAG G with n+O(k1+e) vertices and a constant degree such that even after removing any k vertices from G, the remaining digraph still contains an n-vertex dipath. This paper also proves that for every positive integers n, k and any positive number e, we can explicitly construct a graph H with n + O(k2+e) vertices and a constant degree such that even after removing any k vertices from H, the remaining graph still contains an n-vertex 2-dimensional square mesh.

For a positive integer c, a c-vertex-ranking of a graph G = (V,E) is a labeling of the vertices of G with integers such that, for any label i, deletion of all vertices with labels > i leaves connected components, each having at most c vertices with label i. The c-vertex-ranking problem is to find a c-vertex-ranking of a given graph using the minimum number of ranks. In this paper we give an optimal parallel algorithm for solving the c-vertex-ranking problem on trees in O(log2n) time using linear number of operations on the EREW PRAM model.

An independent set of a graph is a subset of pairwise non-adjacent vertices. A complete bipartite set B is a subset of vertices admitting a bipartition B=X∪Y, such that both X and Y are independent sets, and all vertices of X are adjacent to those of Y. If both X,Y≠∅, then B is called proper. A biclique is a maximal proper complete bipartite set of a graph. When the requirement that X and Y are independent sets of G is dropped, we have a non-induced biclique. We show that it is NP-complete to test whether a subset of the vertices of a graph is part of a biclique. We propose an algorithm that generates all non-induced bicliques of a graph. In addition, we propose specialized efficient algorithms for generating the bicliques of special classes of graphs.