Bounds and Extremal Graphs for Total Dominating Identifying Codes

Abstract

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.