Extremal problems in detectable colorings of connected graphs with cycle rank 2
Let \(G\) be a connected graph with order \(n\geq 3\) and let \(c:E(G) \to\{1,2,\dots, k\}\) be a colouring of the edges of \(G\) for some positive integer \(k\) (adjacent edges may be coloured the same). The colour code of a vertex \(v\) of \(G\) (with respect to \(c)\) is the ordered \(k\)-tuple \(c (v)=a_1a_2\dots a_k\), where \(a_i\) is the number of edges incident with \(v\) that are coloured \(i\) for \(1\leq i\leq k\). The colouring \(c\) is detectable if distinct vertices have distinct colour codes. The detection number \(\det (G)\) of \(G\) is the minimum positive integer \(k\) for which \(G\) has a detectable \(k\)-colouring. A connected graph of order \(n\geq 4\) and size \(m\) is said to have cycle rank 2 if \(m=n+1\). For each integer \(n\geq 4\), let \(D_2(n)\) be the maximum detection number among all connected graphs of order \(n\) with cycle rank 2 and \(d_2(n)\) the minimum detection number among all connected graphs of order \(n\) with cycle rank 2. The numbers \(D_2(n)\) and \(d_2(n)\) are determined for all integers \(n\geq 4\). For integers \(k\geq 2\) and \(n\geq 4\), there exists a connected graph \(G\) with order \(n\) having cycle rank 2 and \(\det(G)=k\) if and only if \(d_2(n)\leq k\leq D_2(n)\). Two conjectures are stated too.
This page was built for publication: Extremal problems in detectable colorings of connected graphs with cycle rank 2
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2369385)
