A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Bounds and Extremal Graphs for Total Dominating Identifying Codes
Tekijät: Foucaud Florent, Lehtilä Tuomo
Kustantaja: ELECTRONIC JOURNAL OF COMBINATORICS
Julkaisuvuosi: 2023
Journal: The Electronic Journal of Combinatorics
Tietokannassa oleva lehden nimi: ELECTRONIC JOURNAL OF COMBINATORICS
Lehden akronyymi: ELECTRON J COMB
Artikkelin numero: P3.15
Vuosikerta: 30
Numero: 3
Sivujen määrä: 30
ISSN: 1077-8926
DOI: https://doi.org/10.37236/11342
Verkko-osoite: https://doi.org/10.37236/11342
Rinnakkaistallenteen osoite: https://research.utu.fi/converis/portal/detail/Publication/180765000
An identifying code C of a graph G is a dominating set of G such that any two distinct vertices of G have distinct closed neighbourhoods within C. The smallest size of an identifying code of G is denoted & gamma;ID(G). When every vertex of G also has a neighbour in C, it is said to be a total dominating identifying code of G, and the smallest size of a total dominating identifying code of G is denoted by & gamma;ID t (G). Extending similar characterizations for identifying codes from the literature, we characterize those graphs G of order n with & gamma;tID(G) = n (the only such connected graph is P3) and & gamma;tID(G) = n - 1 (such graphs either satisfy & gamma;ID(G) = n - 1 or are built from certain such graphs by adding a set of universal vertices, to each of which a private leaf is attached).Then, using bounds from the literature, we remark that any (open and closed) twin-free tree of order n has a total dominating identifying code of size at most 3n4 . This bound is tight, and we characterize the trees reaching it. Moreover, by a new proof, we show that this upper bound actually holds for the larger class of all twin-free graphs of girth at least 5. The cycle C8 also attains the upper bound. We also provide a generalized bound for all graphs of girth at least 5 (possibly with twins).Finally, we relate & gamma;tID (G) to the similar parameter & gamma;ID(G) as well as to the location-domination number of G and its variants, providing bounds that are either tight or almost tight.
Ladattava julkaisu This is an electronic reprint of the original article. |  |
