Home Identifying open codes in trees and 4-cycle-free graphs of given maximum degree

Publications

Identifying open codes in trees and 4-cycle-free graphs of given maximum degree

Year : 2026

Publisher : Elsevier B.V.

Source Title : Discrete Applied Mathematics

Document Type :

Abstract

An identifying open code of a graph G is a set S of vertices that is both a separating open code (that is, NG(u)∩S≠NG(v)∩S for all distinct vertices u and v in G) and a total dominating set (that is, N(v)∩S≠0̸ for all vertices v in G). Such a set exists if and only if the graph G is open twin-free and isolate-free; and the minimum cardinality of an identifying open code in an open twin-free and isolate-free graph G, its identifying open code number, is denoted by γIOC(G). We study the identifying open code number of a graph, in relation with its order and its maximum degree. For Δ a fixed integer at least 3, we show that if G is a connected graph of order n≥5 that contains no 4-cycle and is open twin-free with maximum degree bounded above by Δ, then γIOC(G)≤2Δ−12Δn, unless G is obtained from a star K1,Δ by subdividing every edge exactly once. Moreover, we show that the bound is best possible by constructing graphs that reach the bound when Δ=3, and nearly best possible by another construction when Δ≥4, with identifying open code numbers 2Δ−42Δ−3n.