We consider the following vertex-partition problem on graphs, known as the CLUSTER DELETION (CD) problem: given a graph with real nonnegative edge weights, partition the vertices into clusters (in this case, cliques) to ...

A connected graph G=(V,E) with m edges is called universal antimagic if for each set B of m positive integers there is an bijective function f:E→B such that the function f˜:V→N defined at each vertex v as the sum of all ...

A (0, 1)-matrix has the Consecutive Ones Property (C1P) for the rows if there is a permutation of its columns such that the ones in each row appear consecutively. We say a (0, 1)-matrix is nested if it has the consecutive ...

Hartsfield and Ringel in 1990 conjectured that any connected graph with q >= 2 edges has an edge labeling f with labels in the set {1,..., q}, such that for every two distinct vertices u and v, f(u) not equal= f(v), where ...

A complete set of a graph G is a subset of vertices inducing a complete subgraph. A clique is a maximal complete set. Denote by C(G) the clique family of G. The clique graph of G, denoted by K(G), is the intersection graph ...

Let G = (V, E) be a simple and undirected graph. An edge-coloring is an assignment of colors to the edges of the graph such that any two adjacent edges receive different colors. The chromatic index of a graph G is the ...

We consider two types of graph domination - {k}-domination and k-tuple domination, for a fixed positive integer k - and provide new NP-complete as well as polynomial time solvable instances for their related decision ...

Graph pebbling is a network optimization model for transporting discrete resourcesthat are consumed in transit: the movement of 2 pebbles across an edge consumes one of thepebbles. The pebbling number of a graph is the ...