Source author record

Florent Foucaud

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Discrete Mathematics Data Structures and Algorithms Computational Complexity

Catalog footprint

Research overview

23works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Graph modification for edge-coloured and signed graph homomorphism problems: parameterized and classical complexity

We study the complexity of graph modification problems with respect to homomorphism-based colouring properties of edge-coloured graphs. A homomorphism from edge-coloured graph $G$ to edge-coloured graph $H$ is a vertex-mapping from $G$ to $H$ that preserves adjacencies and edge-colours. We consider the property of having a homomorphism to a fixed edge-coloured graph $H$ . The question we are interested in is: given an edge-coloured graph $G$ , can we perform $k$ graph operations so that the resulting graph admits a homomorphism to $H$ ? The operations we consider are vertex-deletion, edge-deletion and switching (an operation that permutes the colours of the edges incident to a given vertex). Switching plays an important role in the theory of signed graphs, that are 2-edge-coloured graphs whose colours are the signs $+$ and $-$ . We denote the corresponding problems (parameterized by $k$ ) by VD- $H$ -COLOURING, ED- $H$ -COLOURING and SW- $H$ -COLOURING. These problems generalise $H$ -COLOURING (to decide if an input graph admits a homomorphism to a fixed target $H$ ). Our main focus is when $H$ is an edge-coloured graph with at most two vertices, a case that is already interesting as it includes problems such as VERTEX COVER, ODD CYCLE RANSVERSAL and EDGE BIPARTIZATION. For such a graph $H$ , we give a P/NP-c complexity dichotomy for VD- $H$ -COLOURING, ED- $H$ -COLOURING and SW- $H$ -COLOURING. We then address their parameterized complexity. We show that VD- $H$ -COLOURING and ED- $H$ -COLOURING for all such $H$ are FPT. In contrast, already for some $H$ of order 3, unless P=NP, none of the three problems is in XP, since 3-COLOURING is NP-c. We show that SW- $H$ -COLOURING is different: there are three 2-edge-coloured graphs $H$ of order 2 for which SW- $H$ -COLOURING is W-hard, and assuming the ETH, admits no algorithm in time $f(k)n^{o(k)}$ . For the other cases, SW- $H$ -COLOURING is FPT.

preprint2021arXiv

Characterizing extremal graphs for open neighbourhood location-domination

An open neighbourhood locating-dominating set is a set $S$ of vertices of a graph $G$ such that each vertex of $G$ has a neighbour in $S$ , and for any two vertices $u,v$ of $G$ , there is at least one vertex in $S$ that is a neighbour of exactly one of $u$ and $v$ . We characterize those graphs whose only open neighbourhood locating-dominating set is the whole set of vertices. More precisely, we prove that these graphs are exactly the graphs all whose connected components are half-graphs (a half-graph is a special bipartite graph with both parts of the same size, where each part can be ordered so that the open neighbourhoods of consecutive vertices differ by exactly one vertex). This corrects a wrong characterization from the literature.

preprint2021arXiv

Exact square coloring of subcubic planar graphs

We study the exact square chromatic number of subcubic planar graphs. An exact square coloring of a graph G is a vertex-coloring in which any two vertices at distance exactly 2 receive distinct colors. The smallest number of colors used in such a coloring of G is its exact square chromatic number, denoted $χ^{\sharp 2}(G)$ . This notion is related to other types of distance-based colorings, as well as to injective coloring. Indeed, for triangle-free graphs, exact square coloring and injective coloring coincide. We prove tight bounds on special subclasses of planar graphs: subcubic bipartite planar graphs and subcubic K 4-minor-free graphs have exact square chromatic number at most 4. We then turn our attention to the class of fullerene graphs, which are cubic planar graphs with face sizes 5 and 6. We characterize fullerene graphs with exact square chromatic number 3. Furthermore, supporting a conjecture of Chen, Hahn, Raspaud and Wang (that all subcubic planar graphs are injectively 5-colorable) we prove that any induced subgraph of a fullerene graph has exact square chromatic number at most 5. This is done by first proving that a minimum counterexample has to be on at most 80 vertices and then computationally verifying the claim for all such graphs.

preprint2020arXiv

Algorithms and complexity for geodetic sets on planar and chordal graphs

We study the complexity of finding the \emph{geodetic number} on subclasses of planar graphs and chordal graphs. A set $S$ of vertices of a graph $G$ is a \emph{geodetic set} if every vertex of $G$ lies in a shortest path between some pair of vertices of $S$ . The \textsc{Minimum Geodetic Set (MGS)} problem is to find a geodetic set with minimum cardinality of a given graph. The problem is known to remain NP-hard on bipartite graphs, chordal graphs, planar graphs and subcubic graphs. We first study \textsc{MGS} on restricted classes of planar graphs: we design a linear-time algorithm for \textsc{MGS} on solid grids, improving on a $3$ -approximation algorithm by Chakraborty et al. (CALDAM, 2020) and show that it remains NP-hard even for subcubic partial grids of arbitrary girth. This unifies some results in the literature. We then turn our attention to chordal graphs, showing that \textsc{MGS} is fixed parameter tractable for inputs of this class when parameterized by its \emph{tree-width} (which equals its clique number). This implies a polynomial-time algorithm for $k$ -trees, for fixed $k$ . Then, we show that \textsc{MGS} is NP-hard on interval graphs, thereby answering a question of Ekim et al. (LATIN, 2012). As interval graphs are very constrained, to prove the latter result we design a rather sophisticated reduction technique to work around their inherent linear structure.

preprint2020arXiv

On the complexity of Broadcast Domination and Multipacking in digraphs

We study the complexity of the two dual covering and packing distance-based problems Broadcast Domination and Multipacking in digraphs. A dominating broadcast of a digraph $D$ is a function $f:V(D)\to\mathbb{N}$ such that for each vertex $v$ of $D$ , there exists a vertex $t$ with $f(t)>0$ having a directed path to $v$ of length at most $f(t)$ . The cost of $f$ is the sum of $f(v)$ over all vertices $v$ . A multipacking is a set $S$ of vertices of $D$ such that for each vertex $v$ of $D$ and for every integer $d$ , there are at most $d$ vertices from $S$ within directed distance at most $d$ from $v$ . The maximum size of a multipacking of $D$ is a lower bound to the minimum cost of a dominating broadcast of $D$ . Let Broadcast Domination denote the problem of deciding whether a given digraph $D$ has a dominating broadcast of cost at most $k$ , and Multipacking the problem of deciding whether $D$ has a multipacking of size at least $k$ . It is known that Broadcast Domination is polynomial-time solvable for the class of all undirected graphs (that is, symmetric digraphs), while polynomial-time algorithms for Multipacking are known only for a few classes of undirected graphs. We prove that Broadcast Domination and Multipacking are both NP-complete for digraphs, even for planar layered acyclic digraphs of small maximum degree. Moreover, when parameterized by the solution cost/solution size, we show that the problems are W-hard. We also show that Broadcast Domination is FPT on acyclic digraphs, and that it does not admit a polynomial kernel for such inputs, unless the polynomial hierarchy collapses to its third level. In addition, we show that both problems are FPT when parameterized by the solution cost/solution size together with the maximum out-degree, and as well, by the vertex cover number. Finally, we give for both problems polynomial-time algorithms for some subclasses of acyclic digraphs.

preprint2016arXiv

Locating-total dominating sets in twin-free graphs: a conjecture

A total dominating set of a graph $G$ is a set $D$ of vertices of $G$ such that every vertex of $G$ has a neighbor in $D$ . A locating-total dominating set of $G$ is a total dominating set $D$ of $G$ with the additional property that every two distinct vertices outside $D$ have distinct neighbors in $D$ ; that is, for distinct vertices $u$ and $v$ outside $D$ , $N(u) \cap D \ne N(v) \cap D$ where $N(u)$ denotes the open neighborhood of $u$ . A graph is twin-free if every two distinct vertices have distinct open and closed neighborhoods. The location-total domination number of $G$ , denoted $LT(G)$ , is the minimum cardinality of a locating-total dominating set in $G$ . It is well-known that every connected graph of order $n \geq 3$ has a total dominating set of size at most $\frac{2}{3}n$ . We conjecture that if $G$ is a twin-free graph of order $n$ with no isolated vertex, then $LT(G) \leq \frac{2}{3}n$ . We prove the conjecture for graphs without $4$ -cycles as a subgraph. We also prove that if $G$ is a twin-free graph of order $n$ , then $LT(G) \le \frac{3}{4}n$ .

preprint2016arXiv

Location-domination and matching in cubic graphs

A dominating set of a graph $G$ is a set $D$ of vertices of $G$ such that every vertex outside $D$ is adjacent to a vertex in $D$ . A locating-dominating set of $G$ is a dominating set $D$ of $G$ with the additional property that every two distinct vertices outside $D$ have distinct neighbors in $D$ ; that is, for distinct vertices $u$ and $v$ outside $D$ , $N(u) \cap D \neq N(v) \cap D$ where $N(u)$ denotes the open neighborhood of $u$ . A graph is twin-free if every two distinct vertices have distinct open and closed neighborhoods. The location-domination number of $G$ , denoted $γ_L(G)$ , is the minimum cardinality of a locating-dominating set in $G$ . Garijo, Gonzalez and Marquez [Applied Math. Computation 249 (2014), 487--501] posed the conjecture that for $n$ sufficiently large, the maximum value of the location-domination number of a twin-free, connected graph on $n$ vertices is equal to $\lfloor \frac{n}{2} \rfloor$ . We propose the related (stronger) conjecture that if $G$ is a twin-free graph of order $n$ without isolated vertices, then $γ_L(G)\leq \frac{n}{2}$ . We prove the conjecture for cubic graphs. We rely heavily on proof techniques from matching theory to prove our result.

preprint2016arXiv

Location-domination in line graphs

A set $D$ of vertices of a graph $G$ is locating if every two distinct vertices outside $D$ have distinct neighbors in $D$ ; that is, for distinct vertices $u$ and $v$ outside $D$ , $N(u) \cap D \neq N(v) \cap D$ , where $N(u)$ denotes the open neighborhood of $u$ . If $D$ is also a dominating set (total dominating set), it is called a locating-dominating set (respectively, locating-total dominating set) of $G$ . A graph $G$ is twin-free if every two distinct vertices of $G$ have distinct open and closed neighborhoods. It is conjectured [D. Garijo, A. Gonzalez and A. Marquez, The difference between the metric dimension and the determining number of a graph. Applied Mathematics and Computation 249 (2014), 487--501] and [F. Foucaud and M. A. Henning. Locating-total dominating sets in twin-free graphs: a conjecture. The Electronic Journal of Combinatorics 23 (2016), P3.9] respectively, that any twin-free graph $G$ without isolated vertices has a locating-dominating set of size at most one-half its order and a locating-total dominating set of size at most two-thirds its order. In this paper, we prove these two conjectures for the class of line graphs. Both bounds are tight for this class, in the sense that there are infinitely many connected line graphs for which equality holds in the bounds.

preprint2016arXiv

The complexity of signed graph and edge-coloured graph homomorphisms

We study homomorphism problems of signed graphs from a computational point of view. A signed graph $(G,Σ)$ is a graph $G$ where each edge is given a sign, positive or negative; $Σ\subseteq E(G)$ denotes the set of negative edges. Thus, $(G, Σ)$ is a $2$ -edge-coloured graph with the property that the edge-colours, $\{+, -\}$ , form a group under multiplication. Central to the study of signed graphs is the operation of switching at a vertex, that results in changing the sign of each incident edge. We study two types of homomorphisms of a signed graph $(G,Σ)$ to a signed graph $(H,Π)$ : ec-homomorphisms and s-homomorphisms. Each is a standard graph homomorphism of $G$ to $H$ with some additional constraint. In the former, edge-signs are preserved. In the latter, edge-signs are preserved after the switching operation has been applied to a subset of vertices of $G$ . We prove a dichotomy theorem for s-homomorphism problems for a large class of (fixed) target signed graphs $(H,Π)$ . Specifically, as long as $(H,Π)$ does not contain a negative (respectively a positive) loop, the problem is polynomial-time solvable if the core of $(H,Π)$ has at most two edges, and is NP-complete otherwise. (Note that this covers all simple signed graphs.) The same dichotomy holds if $(H,Π)$ has no negative digons, and we conjecture that it holds always. In our proofs, we reduce s-homomorphism problems to certain ec-homomorphism problems, for which we are able to show a dichotomy. In contrast, we prove that a dichotomy theorem for ec-homomorphism problems (even when restricted to bipartite target signed graphs) would settle the dichotomy conjecture of Feder and Vardi.

preprint2015arXiv

Complexity of Grundy coloring and its variants

The Grundy number of a graph is the maximum number of colors used by the greedy coloring algorithm over all vertex orderings. In this paper, we study the computational complexity of GRUNDY COLORING, the problem of determining whether a given graph has Grundy number at least $k$ . We also study the variants WEAK GRUNDY COLORING (where the coloring is not necessarily proper) and CONNECTED GRUNDY COLORING (where at each step of the greedy coloring algorithm, the subgraph induced by the colored vertices must be connected). We show that GRUNDY COLORING can be solved in time $O^*(2.443^n)$ and WEAK GRUNDY COLORING in time $O^*(2.716^n)$ on graphs of order $n$ . While GRUNDY COLORING and WEAK GRUNDY COLORING are known to be solvable in time $O^*(2^{O(wk)})$ for graphs of treewidth $w$ (where $k$ is the number of colors), we prove that under the Exponential Time Hypothesis (ETH), they cannot be solved in time $O^*(2^{o(w\log w)})$ . We also describe an $O^*(2^{2^{O(k)}})$ algorithm for WEAK GRUNDY COLORING, which is therefore $\fpt$ for the parameter $k$ . Moreover, under the ETH, we prove that such a running time is essentially optimal (this lower bound also holds for GRUNDY COLORING). Although we do not know whether GRUNDY COLORING is in $\fpt$, we show that this is the case for graphs belonging to a number of standard graph classes including chordal graphs, claw-free graphs, and graphs excluding a fixed minor. We also describe a quasi-polynomial time algorithm for GRUNDY COLORING and WEAK GRUNDY COLORING on apex-minor graphs. In stark contrast with the two other problems, we show that CONNECTED GRUNDY COLORING is $\np$-complete already for $k=7$ colors.

preprint2015arXiv

Locating-dominating sets and identifying codes in graphs of girth at least 5

Locating-dominating sets and identifying codes are two closely related notions in the area of separating systems. Roughly speaking, they consist in a dominating set of a graph such that every vertex is uniquely identified by its neighbourhood within the dominating set. In this paper, we study the size of a smallest locating-dominating set or identifying code for graphs of girth at least 5 and of given minimum degree. We use the technique of vertex-disjoint paths to provide upper bounds on the minimum size of such sets, and construct graphs who come close to meet these bounds.

preprint2015arXiv

Locating-dominating sets in twin-free graphs

A locating-dominating set of a graph $G$ is a dominating set $D$ of $G$ with the additional property that every two distinct vertices outside $D$ have distinct neighbors in $D$ ; that is, for distinct vertices $u$ and $v$ outside $D$ , $N(u) \cap D \ne N(v) \cap D$ where $N(u)$ denotes the open neighborhood of $u$ . A graph is twin-free if every two distinct vertices have distinct open and closed neighborhoods. The location-domination number of $G$ , denoted $γ_L(G)$ , is the minimum cardinality of a locating-dominating set in $G$ . It is conjectured [D. Garijo, A. González and A. Márquez. The difference between the metric dimension and the determining number of a graph. Applied Mathematics and Computation 249 (2014), 487--501] that if $G$ is a twin-free graph of order $n$ without isolated vertices, then $γ_L(G)\le \frac{n}{2}$ . We prove the general bound $γ_L(G)\le \frac{2n}{3}$ , slightly improving over the $\lfloor\frac{2n}{3}\rfloor+1$ bound of Garijo et al. We then provide constructions of graphs reaching the $\frac{n}{2}$ bound, showing that if the conjecture is true, the family of extremal graphs is a very rich one. Moreover, we characterize the trees $G$ that are extremal for this bound. We finally prove the conjecture for split graphs and co-bipartite graphs.

preprint2015arXiv

On powers of interval graphs and their orders

It was proved by Raychaudhuri in 1987 that if a graph power $G^{k-1}$ is an interval graph, then so is the next power $G^k$ . This result was extended to $m$ -trapezoid graphs by Flotow in 1995. We extend the statement for interval graphs by showing that any interval representation of $G^{k-1}$ can be extended to an interval representation of $G^k$ that induces the same left endpoint and right endpoint orders. The same holds for unit interval graphs. We also show that a similar fact does not hold for trapezoid graphs.

preprint2014arXiv

Centroidal bases in graphs

We introduce the notion of a centroidal locating set of a graph $G$ , that is, a set $L$ of vertices such that all vertices in $G$ are uniquely determined by their relative distances to the vertices of $L$ . A centroidal locating set of $G$ of minimum size is called a centroidal basis, and its size is the centroidal dimension $CD(G)$ . This notion, which is related to previous concepts, gives a new way of identifying the vertices of a graph. The centroidal dimension of a graph $G$ is lower- and upper-bounded by the metric dimension and twice the location-domination number of $G$ , respectively. The latter two parameters are standard and well-studied notions in the field of graph identification. We show that for any graph $G$ with $n$ vertices and maximum degree at least~2, $(1+o(1))\frac{\ln n}{\ln\ln n}\leq CD(G) \leq n-1$ . We discuss the tightness of these bounds and in particular, we characterize the set of graphs reaching the upper bound. We then show that for graphs in which every pair of vertices is connected via a bounded number of paths, $CD(G)=Ω\left(\sqrt{|E(G)|}\right)$ , the bound being tight for paths and cycles. We finally investigate the computational complexity of determining $CD(G)$ for an input graph $G$ , showing that the problem is hard and cannot even be approximated efficiently up to a factor of $o(\log n)$ . We also give an $O\left(\sqrt{n\ln n}\right)$ -approximation algorithm.

preprint2014arXiv

Large subgraphs without short cycles

We study two extremal problems about subgraphs excluding a family $\F$ of graphs. i) Among all graphs with $m$ edges, what is the smallest size $f(m,\F)$ of a largest $\F$--free subgraph? ii) Among all graphs with minimum degree $δ$ and maximum degree $Δ$ , what is the smallest minimum degree $h(δ,Δ,\F)$ of a spanning $\F$--free subgraph with largest minimum degree? These questions are easy to answer for families not containing any bipartite graph. We study the case where $\F$ is composed of all even cycles of length at most $2r$ , $r\geq 2$ . In this case, we give bounds on $f(m,\F)$ and $h(δ,Δ,\F)$ that are essentially asymptotically tight up to a logarithmic factor. In particular for every graph $G$ , we show the existence of subgraphs with arbitrarily high girth, and with either many edges or large minimum degree. These subgraphs are created using probabilistic embeddings of a graph into extremal graphs.

preprint2013arXiv

Random subgraphs make identification affordable

An identifying code of a graph is a dominating set which uniquely determines all the vertices by their neighborhood within the code. Whereas graphs with large minimum degree have small domination number, this is not the case for the identifying code number (the size of a smallest identifying code), which indeed is not even a monotone parameter with respect to graph inclusion. We show that every graph $G$ with $n$ vertices, maximum degree $Δ=ω(1)$ and minimum degree $δ\geq c\logΔ$ , for some constant $c>0$ , contains a large spanning subgraph which admits an identifying code with size $O\left(\frac{n\logΔ}δ\right)$ . In particular, if $δ=Θ(n)$ , then $G$ has a dense spanning subgraph with identifying code $O\left(\log n\right)$ , namely, of asymptotically optimal size. The subgraph we build is created using a probabilistic approach, and we use an interplay of various random methods to analyze it. Moreover we show that the result is essentially best possible, both in terms of the number of deleted edges and the size of the identifying code.

preprint2012arXiv

Bounds for identifying codes in terms of degree parameters

An identifying code is a subset of vertices of a graph such that each vertex is uniquely determined by its neighbourhood within the identifying code. If $\M(G)$ denotes the minimum size of an identifying code of a graph $G$ , it was conjectured by F. Foucaud, R. Klasing, A. Kosowski and A. Raspaud that there exists a constant $c$ such that if a connected graph $G$ with $n$ vertices and maximum degree $d$ admits an identifying code, then $\M(G)\leq n-\tfrac{n}{d}+c$. We use probabilistic tools to show that for any $d\geq 3$ , $\M(G)\leq n-\tfrac{n}{Θ(d)}$ holds for a large class of graphs containing, among others, all regular graphs and all graphs of bounded clique number. This settles the conjecture (up to constants) for these classes of graphs. In the general case, we prove $\M(G)\leq n-\tfrac{n}{Θ(d^{3})}$. In a second part, we prove that in any graph $G$ of minimum degree $δ$ and girth at least 5, $\M(G)\leq(1+o_δ(1))\tfrac{3\logδ}{2δ}n$. Using the former result, we give sharp estimates for the size of the minimum identifying code of random $d$ -regular graphs, which is about $\tfrac{\log d}{d}n$ .

preprint2012arXiv

Characterizing extremal digraphs for identifying codes and extremal cases of Bondy's theorem on induced subsets

An identifying code of a (di)graph $G$ is a dominating subset $C$ of the vertices of $G$ such that all distinct vertices of $G$ have distinct (in)neighbourhoods within $C$ . In this paper, we classify all finite digraphs which only admit their whole vertex set in any identifying code. We also classify all such infinite oriented graphs. Furthermore, by relating this concept to a well known theorem of A. Bondy on set systems we classify the extremal cases for this theorem.

preprint2012arXiv

Identifying codes in line graphs

An identifying code of a graph is a subset of its vertices such that every vertex of the graph is uniquely identified by the set of its neighbours within the code. We study the edge-identifying code problem, i.e. the identifying code problem in line graphs. If $\ID(G)$ denotes the size of a minimum identifying code of an identifiable graph $G$ , we show that the usual bound $\ID(G)\ge \lceil\log_2(n+1)\rceil$, where $n$ denotes the order of $G$ , can be improved to $Θ(\sqrt{n})$ in the class of line graphs. Moreover, this bound is tight. We also prove that the upper bound $\ID(\mathcal{L}(G))\leq 2|V(G)|-5$, where $\mathcal{L}(G)$ is the line graph of $G$ , holds (with two exceptions). This implies that a conjecture of R. Klasing, A. Kosowski, A. Raspaud and the first author holds for a subclass of line graphs. Finally, we show that the edge-identifying code problem is NP-complete, even for the class of planar bipartite graphs of maximum degree~3 and arbitrarily large girth.

preprint2012arXiv

Locally identifying colourings for graphs with given maximum degree

A proper vertex-colouring of a graph G is said to be locally identifying if for any pair u,v of adjacent vertices with distinct closed neighbourhoods, the sets of colours in the closed neighbourhoods of u and v are different. We show that any graph G has a locally identifying colouring with $2Δ^2-3Δ+3$ colours, where $Δ$ is the maximum degree of G, answering in a positive way a question asked by Esperet et al. We also provide similar results for locally identifying colourings which have the property that the colours in the neighbourhood of each vertex are all different and apply our method to the class of chordal graphs.

preprint2012arXiv

On the size of identifying codes in triangle-free graphs

In an undirected graph $G$ , a subset $C\subseteq V(G)$ such that $C$ is a dominating set of $G$ , and each vertex in $V(G)$ is dominated by a distinct subset of vertices from $C$ , is called an identifying code of $G$ . The concept of identifying codes was introduced by Karpovsky, Chakrabarty and Levitin in 1998. For a given identifiable graph $G$ , let $\M(G)$ be the minimum cardinality of an identifying code in $G$ . In this paper, we show that for any connected identifiable triangle-free graph $G$ on $n$ vertices having maximum degree $Δ\geq 3$ , $\M(G)\le n-\tfrac{n}{Δ+o(Δ)}$. This bound is asymptotically tight up to constants due to various classes of graphs including $(Δ-1)$ -ary trees, which are known to have their minimum identifying code of size $n-\tfrac{n}{Δ-1+o(1)}$ . We also provide improved bounds for restricted subfamilies of triangle-free graphs, and conjecture that there exists some constant $c$ such that the bound $\M(G)\le n-\tfrac{n}Δ+c$ holds for any nontrivial connected identifiable graph $G$ .

preprint2011arXiv

An improved lower bound for (1,<=2)-identifying codes in the king grid

We call a subset $C$ of vertices of a graph $G$ a $(1,\leq \ell)$ -identifying code if for all subsets $X$ of vertices with size at most $\ell$ , the sets $\{c\in C |\exists u \in X, d(u,c)\leq 1\}$ are distinct. The concept of identifying codes was introduced in 1998 by Karpovsky, Chakrabarty and Levitin. Identifying codes have been studied in various grids. In particular, it has been shown that there exists a $(1,\leq 2)$ -identifying code in the king grid with density 3/7 and that there are no such identifying codes with density smaller than 5/12. Using a suitable frame and a discharging procedure, we improve the lower bound by showing that any $(1,\leq 2)$ -identifying code of the king grid has density at least 47/111.

preprint2011arXiv

Extremal graphs for the identifying code problem

An identifying code of a graph G is a dominating set C such that every vertex x of G is distinguished from all other vertices by the set of vertices in C that are at distance at most 1 from x. The problem of finding an identifying code of minimum possible size turned out to be a challenging problem. It was proved by N. Bertrand that if a graph on n vertices with at least one edge admits an identifying code, then a minimum identifying code has size at most n-1. Some classes of graphs whose smallest identifying code is of size n-1 were already known, and few conjectures were formulated to classify all these graphs. In this paper, disproving these conjectures, we classify all finite graphs for which all but one of the vertices are needed to form an identifying code. We also classify all infinite graphs needing the whole set of vertices in any identifying code. New upper bounds in terms of the number of vertices and the maximum degree of a graph are also provided.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Florent Foucaud

Research overview

Is this your work?

23 publications

Graph modification for edge-coloured and signed graph homomorphism problems: parameterized and classical complexity

Characterizing extremal graphs for open neighbourhood location-domination

Exact square coloring of subcubic planar graphs

Algorithms and complexity for geodetic sets on planar and chordal graphs

On the complexity of Broadcast Domination and Multipacking in digraphs

Locating-total dominating sets in twin-free graphs: a conjecture

Location-domination and matching in cubic graphs

Location-domination in line graphs

The complexity of signed graph and edge-coloured graph homomorphisms

Complexity of Grundy coloring and its variants

Locating-dominating sets and identifying codes in graphs of girth at least 5

Locating-dominating sets in twin-free graphs

On powers of interval graphs and their orders

Centroidal bases in graphs

Large subgraphs without short cycles

Random subgraphs make identification affordable

Bounds for identifying codes in terms of degree parameters

Characterizing extremal digraphs for identifying codes and extremal cases of Bondy's theorem on induced subsets

Identifying codes in line graphs

Locally identifying colourings for graphs with given maximum degree

On the size of identifying codes in triangle-free graphs

An improved lower bound for (1,<=2)-identifying codes in the king grid

Extremal graphs for the identifying code problem

See the researcher in context

Building this map preview