Buscar
Mostrando ítems 1-10 de 49
On some graph classes related to perfect graphs: A survey
(Elsevier, 2020)
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 ...
On some graph classes related to perfect graphs: A survey
(Elsevier B.V., 2020)
© 2019 Elsevier B.V.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 ...
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 ...
Graphs admitting antimagic labeling for arbitrary sets of positive integers
(Elsevier, 2017)
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 ...
Graphs admitting antimagic labeling for arbitrary sets of positive numbers
(Elsevier, 2020)
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 ...
TSP Tours in Cubic Graphs: Beyond 4/3 Read More: http://epubs.siam.org/doi/abs/10.1137/140972925
(Society for Industrial and Applied Mathematics, 2015)
After a sequence of improvements Boyd et al. [TSP on cubic and subcubic graphs, Integer Programming and Combinatorial Optimization, Lecture Notes in Comput. Sci. 6655, Springer, Heidelberg, 2011, pp. 65-77] proved that any ...
Weighted antimagic labeling
(Elsevier, 2018-08)
A graph G = (V, E) is weighted-k-antimagic if for each w : V -> R, there is an injective function f : E -> {1,...,vertical bar E vertical bar + k} such that the following sums are all distinct: for each vertex u, Sigma(v:uv ...
Quasi-polynomial time approximation schemes for packing and covering problems in planar graphs
(Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2018)
We consider two optimization problems in planar graphs. In Maximum Weight Independent Set of Objects we are given a graph G and a family D of objects, each being a
connected subgraph of G with a prescribed weight, and the ...
The chromatic polynomial of fatgraphs and its categorification
(ACADEMIC PRESS INC ELSEVIER SCIENCE, 2008-03-01)
Motivated by Khovanov homology and relations between the Jones polynomial and graph polynomials, we construct a homology theory for embedded graphs from which the chromatic polynomial can be recovered as the Euler ...