2024/07/12 by Chakraborty, Dipayan, Foucaud, Florent, Henning, Michael A.
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2407.09692
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 ≠ ∅ 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 is denoted by γ^\rm \small IOC(G). We study the smallest size of an identifying open code of a graph, in relation with its order and its maximum degree. For Δ a fixed integer at least 3, 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 we show that γ^\rm \small IOC(G) ≤ ( \frac2Δ- 1Δ ) 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.