Powered by OpenAIRE graph
Found an issue? Give us feedback
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/ Electronic Journal o...arrow_drop_down
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
Electronic Journal of Combinatorics
Article . 2026 . Peer-reviewed
Data sources: Crossref
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
HAL AMU
Article . 2026
Data sources: HAL AMU
DBLP
Article . 2026
Data sources: DBLP
versions View all 4 versions
addClaim

A Note on Partitioning the Vertex Set of a Graph into a Dominating Set and a Locating Dominating Set

Authors: Chakraborty, Dipayan; Foucaud, Florent; Henning, Michael; Laihonen, Tero;

A Note on Partitioning the Vertex Set of a Graph into a Dominating Set and a Locating Dominating Set

Abstract

A set $S$ of vertices in a graph $G$ is a dominating set of $G$ if every vertex not in $S$ has a neighbor in $S$, where two vertices are neighbors if they are adjacent. The domination number, $\gamma(G)$, of $G$ is the minimum cardinality among all dominating sets of $G$. Given a set $S$ of vertices of a graph $G$, two vertices are located by $S$ if they have distinct sets of neighbors in $S$. Moreover, if $S$ locates every pair of vertices not in $S$, then it is called a locating set of $G$. A locating dominating set of $G$ is both a dominating and a locating set of $G$. The locating domination number, $\gamma^{\rm LD} $, is the minimum cardinality among all locating dominating sets of $G$. A notable conjecture in the study of locating dominating sets is to show that the locating domination number of an isolate-free and twin-free graph $G$ of order $n$ is at most $\frac{1}{2}n$. So far, the best approximation to this $\frac{1}{2}n$-upper bound conjecture is known to be $\left \lceil \frac{5}{8}n \right \rceil$. In fact, much in line with the conjecture, an even stronger reformulation proposed in the literature is to ask if it is possible to partition the vertex set of an isolate-free and twin-free graph into two locating sets. However, such partitions into locating sets may not exist if the graph is also allowed to have twins. Continuing with this line of research, we show that if $G$ is an isolate-free (and not necessarily twin-free) graph, then the vertex set of $G$ can be partitioned into a dominating set and a locating dominating set. As a consequence, we infer that every isolate-free graph $G$ of order~$n$ satisfies $\gamma(G) + \gamma^{\rm LD} \le n$, and we show that the last bound is tight. Moreover, our proof of the existence of a partition of the vertex set of an isolate-free graph into a dominating and a locating dominating set also provides a polynomial-time algorithm to construct such a partition.

Country
France
Keywords

[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], Locating dominating set, Dominating set, vertex partitions

  • BIP!
    Impact byBIP!
    selected citations
    These citations are derived from selected sources.
    This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    0
    popularity
    This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
    Average
    influence
    This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    Average
    impulse
    This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
    Average
Powered by OpenAIRE graph
Found an issue? Give us feedback
selected citations
These citations are derived from selected sources.
This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Citations provided by BIP!
popularity
This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
0
Average
Average
Average
Green
gold