Buscar
Mostrando ítems 1-10 de 23
Artículo
Monochromatic geometric k-factors for bicolored point sets with auxiliary points
(2014)
Given a bicolored point set S, it is not always possible to construct a monochromatic geometric planar k-factor of S. We consider the problem of finding such a k-factor of S by using auxiliary points. Two types are considered: ...
Artículo
On the determining number and the metric dimension of graphs
(Combinatorics.org, 2010)
This paper initiates a study on the problem of computing the difference between the metric dimension and the determining number of graphs. We provide new proofs and results on the determining number of trees and Cartesian ...
Artículo
Stabbers of line segments in the plane
(2011)
The problem of computing a representation of the stabbing lines of a set S of segments in the plane was solved by Edelsbrunner et al. We provide efficient algorithms for the following problems: computing the stabbing wedges ...
Artículo
Distinguishing graphs by their left and right homomorphism profiles
(Elsevier, 2011)
We introduce a new property of graphs called ‘q-state Potts unique-ness’ and relate it to chromatic and Tutte uniqueness, and also to ‘chromatic–flow uniqueness’, recently studied by Duan, Wu and Yu. We establish for ...
Artículo
Resolving sets for breaking symmetries of graphs
(Cornell University, 2014)
This paper deals with the maximum value of the difference between the determining number and the metric dimension of a graph as a function of its order. Our technique requires to use locating-dominating sets, and perform ...
Artículo
Polynomial graph invariants from homomorphism numbers
(Elsevier, 2016)
We give a new method of generating strongly polynomial sequences of graphs, i.e., sequences (Hk) indexed by a tuple k = (k1, . . . , kh) of positive integers, with the property that, for each fixed graph G, there is a ...
Artículo
On the metric dimension, the upper dimension and the resolving number of graphs
(2013)
This paper deals with three resolving parameters: the metric dimension, the upper dimension and the resolving number. We first answer a question raised by Chartrand and Zhang asking for a characterization of the graphs ...
Artículo
The resolving number of a graph
(2013)
We study a graph parameter related to resolving sets and metric dimension, namely the resolving number, introduced by Chartrand, Poisson and Zhang. First, we establish an important difference between the two parameters: ...
Artículo
Contractors for flows
(Elsevier, 2011)
We answer a question raised by Lovász and B. Szegedy [Contractors and connectors in graph algebras, J. Graph Theory 60:1 (2009)] asking for a contractor for the graph parameter counting the number of B-flows of a graph, ...
Artículo