Buscar
Mostrando ítems 11-20 de 403
Powers of cycles, powers of paths, and distance graphs
(Elsevier Science, 2011-04)
In 1988, Golumbic and Hammer characterized the powers of cycles, relating them to circular arc graphs. We extend their results and propose several further structural characterizations for both powers of cycles and powers ...
p-BOX: A new graph model
(2015)
In this document, we study the scope of the following graph model: each vertex is assigned to a box in Rd and to a
representative element that belongs to that box. Two vertices are connected by an edge if and only if its ...
Balancedness of some subclasses of circular-arc graphs
(Elsevier Science, 2010-08)
A graph is balanced if its clique-vertex incidence matrix is balanced, i.e., it does not contain a square submatrix of odd order with exactly two ones per row and per column. Interval graphs, obtained as intersection graphs ...
Minimal proper interval completions
(2008)
Given an arbitrary graph and a proper interval graph with we say that H is a proper interval completion of G. The graph H is called a minimal proper interval completion of G if, for any sandwich graph with , is not a ...
The eternal dominating set problem for interval graphs
(Elsevier Science, 2019-06)
We prove that, in games in which all the guards move at the same turn, the eternal domination and the clique-connected cover numbers coincide for interval graphs. A linear algorithm for the eternal dominating set problem ...
On weighted clique graphs
(2011)
Probe interval graphs and probe unit interval graphs on superclasses of cographs
(DISCRETE MATHEMATICS THEORETICAL COMPUTER SCIENCE, 2013)
Characterization of classical graph classes by weighted clique graphs
(Elsevier Science, 2014-03)
Given integers m1,…,mℓ, the weighted clique graph of G is the clique graph K(G), in which there is a weight assigned to each complete set S of size mi of K(G), for each i=1,…,ℓ. This weight equals the cardinality of the ...
Minimal Proper Interval Completions
(ELSEVIER SCIENCE BV, 2008-05-31)
Given an arbitrary graph G = (V,E) and a proper interval
graph H = (V,F) with E ⊆ F we say that H is a proper interval completion
of G. The graph H is called a minimal proper interval completion of
G if, for any sandwich ...