VLDB 2026 Research / reviewers in the wild / expert
Petru Valicov
dblp:71/8037
· DBLP profile ↗
10ranked-venue papers
0as first author
2since 2021 · last 2021
—ORCID · none
Domains — the database's venue-derived domains; a paper can count in several
Theory of computation · 10 · 2 since 2021Databases, data management, data science and information retrieval · 1
| Year | Publication | Venue | Position |
|---|---|---|---|
| 2021 | Cliques in exact distance powers of graphs of given maximum degreeabstractThe exact distance p-power of a graph G, denoted G[#p], is a graph on vertex set V(G) in which two vertices are adjacent if they are at distance exactly p in G. Given integers k and p, we define f(k, p) to be the maximum possible order of a clique in the exact distance p-powers of graphs with maximum degree k + 1. It is easily observed that f(k, 2) ≤ k2 + k + 1. We prove that equality may only hold if a connected component of G is isomorphic to a member of the class Pk of incidence graphs of finite projective k-geometries. (These famous combinatorial structures are known to exist when k is a prime power, and are conjectured not to exist for other values of k.) We then study the case of graphs of maximum degree k + 1 with clique number k2 + k. One way to obtain such a graph is to remove a vertex from a graph in P k; we call Pk' the class of all such resulting graphs. We prove that for any graph G of maximum degree k + 1 whose exact square has a (k2 + k)-clique, either G has a subgraph isomorphic to a graph in P’k, or a connected component of G is a (k + 1)-regular bipartite graph of order 2(k2 + k). We call Ok the class of such bipartite graphs, and study their structural properties. These properties imply that (if they exist) the graphs in Ok must be highly symmetric. Using this structural information, we show that O2 contains only one graph, known as the Franklin graph. We then show that O3 also consists of a single graph, which we build. Furthermore, we show that O4 and O5 are empty. For general values of p, we prove that f(k, p) ≤ (k + 1)k[p/2] + 1, and that the bound is tight for every odd integer p ≥ 3. This implies that f(k, 2) = f(k, 3) whenever there exists a finite projective k-geometry, however, in such a case, the bound of f(k, 3) could also be reached by highly symmetric graphs built from a finite k-geometry, which is not the case for other values of k. Florent Foucaud, Suchismita Mishra 0001, N. Narayanan 0001, Reza Naserasr, Petru Valicov |
LAGOS | 5 |
| 2021 | Exact square coloring of subcubic planar graphs
Florent Foucaud, Hervé Hocquard, Suchismita Mishra 0001, N. Narayanan 0001, Reza Naserasr, Éric Sopena, Petru Valicov |
Discret. Appl. Math. | 7 |
| 2020 | Enumerating k-Arc-Connected Orientations
Sarah Blind, Kolja B. Knauer, Petru Valicov |
Algorithmica | 3 |
| 2017 | Identification, Location-Domination and Metric Dimension on Interval and Permutation Graphs. II. Algorithms and Complexity
Florent Foucaud, George B. Mertzios, Reza Naserasr, Aline Parreau, Petru Valicov |
Algorithmica | 5 |
| 2017 | Identification, location-domination and metric dimension on interval and permutation graphs. I. Bounds
Florent Foucaud, George B. Mertzios, Reza Naserasr, Aline Parreau, Petru Valicov |
Theor. Comput. Sci. | 5 |
| 2015 | Algorithms and Complexity for Metric Dimension and Location-domination on Interval and Permutation Graphs
Florent Foucaud, George B. Mertzios, Reza Naserasr, Aline Parreau, Petru Valicov |
WG | 5 |
| 2014 | Strong edge-colouring of sparse planar graphs
Julien Bensmail, Ararat Harutyunyan, Hervé Hocquard, Petru Valicov |
Discret. Appl. Math. | 4 |
| 2013 | On strong edge-colouring of subcubic graphs
Hervé Hocquard, Mickaël Montassier, André Raspaud, Petru Valicov |
Discret. Appl. Math. | 4 |
| 2013 | Strong edge-colouring and induced matchings
Hervé Hocquard, Pascal Ochem, Petru Valicov |
Inf. Process. Lett. | 3 |
| 2011 | Strong edge colouring of subcubic graphs
Hervé Hocquard, Petru Valicov |
Discret. Appl. Math. | 2 |