Bounds and Extremal Graphs for Total Dominating Identifying Codes



: Foucaud Florent, Lehtilä Tuomo

Publisher: ELECTRONIC JOURNAL OF COMBINATORICS

: 2023

: The Electronic Journal of Combinatorics

: ELECTRONIC JOURNAL OF COMBINATORICS

: ELECTRON J COMB

: P3.15

: 30

: 3

: 30

: 1077-8926

DOI: https://doi.org/10.37236/11342

: https://doi.org/10.37236/11342

: 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.

Last updated on 2024-26-11 at 12:35