Buscar
Mostrando ítems 11-20 de 16470
Strong cliques and equistability of EPT graphs
(Elsevier Science, 2016-04)
In this paper, we characterize the equistable graphs within the class of EPT graphs, the edge-intersection graphs of paths in a tree. This result generalizes a previously known characterization of equistable line graphs. ...
On second iterated clique graphs that are also third iterated clique graphs
(Elsevier, 2015-12)
Iterated clique graphs arise when the clique operator is applied to a graph more than once. Determining whether a graph is a clique graph or an iterated clique graph is usually a difficult task. The fact that being a clique ...
On some graph classes related to perfect graphs: A survey
(Elsevier Science, 2020-07-15)
Perfect graphs form a well-known class of graphs introduced by Berge in the 1960s in terms of a min–max type equality involving two famous graph parameters. In this work, we survey certain variants and subclasses of perfect ...
Complexity of the cluster deletion problem on subclasses of chordal graphs
(Elsevier Science, 2015-10)
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 ...
Shifts of the stable Kneser graphs and hom-idempotence
(Academic Press Ltd - Elsevier Science Ltd, 2017-05)
A graph G is said to be hom-idempotent if there is a homomorphism from G2 to G, and weakly hom-idempotent if for some n≥1 there is a homomorphism from Gn+1 to Gn. Larose et al. (1998) proved that Kneser graphs KG(n,k) are ...
On weighted clique graphs
(2011)
On probe 2-clique graphs and probe diamond-free graphs
(Discrete Mathematics and Theoretical Computer Science, 2015)
Given a class G of graphs, probe G graphs are defined as follows. A graph G is probe G if there exists a partition of its vertices into a set of probe vertices and a stable set of nonprobe vertices in such a way that ...
Colouring exact distance graphs of chordal graphs
(Elsevier, 2020)
For a graph G = (V, E) and positive integer p, the exact distance-p graph G([hp]) is the graph with vertex set V and with an edge between vertices x and y if and only if x and y have distance p. Recently, there has been ...