A1 Refereed original research article in a scientific journal
Bounds and Extremal Graphs for Total Dominating Identifying Codes
Authors: Foucaud Florent, Lehtilä Tuomo
Publisher: ELECTRONIC JOURNAL OF COMBINATORICS
Publication year: 2023
Journal: The Electronic Journal of Combinatorics
Journal name in source: ELECTRONIC JOURNAL OF COMBINATORICS
Journal acronym: ELECTRON J COMB
Article number: P3.15
Volume: 30
Issue: 3
Number of pages: 30
ISSN: 1077-8926
DOI: https://doi.org/10.37236/11342(external)
Web address : https://doi.org/10.37236/11342(external)
Self-archived copy’s web address: https://research.utu.fi/converis/portal/detail/Publication/180765000(external)
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.
Downloadable publication This is an electronic reprint of the original article. |  |
