Computer Science – Discrete Mathematics
Scientific paper
2011-03-19
The Electronic Journal of Combinatorics 19 (2012) P32
Computer Science
Discrete Mathematics
Scientific paper
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}{\Theta(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}{\Theta(d^{3})}$. In a second part, we prove that in any graph $G$ of minimum degree $\delta$ and girth at least 5, $\M(G)\leq(1+o_\delta(1))\tfrac{3\log\delta}{2\delta}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$.
Foucaud Florent
Perarnau Guillem
No associations
LandOfFree
Bounds for identifying codes in terms of degree parameters does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Bounds for identifying codes in terms of degree parameters, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Bounds for identifying codes in terms of degree parameters will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-198580