×

A note on the total detection numbers of cycles. (English) Zbl 1311.05060

Summary: Let \(G\) be a connected graph of size at least 2 and \(c :E(G)\to\{0, 1,\dots, k- 1\}\) an edge coloring (or labeling) of \(G\) using \(k\) labels, where adjacent edges may be assigned the same label. For each vertex \(v\) of \(G\), the color code of \(v\) with respect to \(c\) is the \(k\)-vector code\((v) = (a_{0}, a_{1},\dots, a_{k-1})\), where \(a_i\) is the number of edges incident with \(v\) that are labeled \(i\) for \(0 \leq i \leq k - 1\). The labeling \(c\) is called a detectable labeling if distinct vertices in \(G\) have distinct color codes. The value \(\mathrm{val}(c)\) of a detectable labeling \(c\) of a graph \(G\) is the sum of the labels assigned to the edges in \(G\). The total detection number \(\mathrm{td}(G)\) of \(G\) is defined by \(\mathrm{td}(G) = \min\{\mathrm{val}(c)\}\), where the minimum is taken over all detectable labelings \(c\) of \(G\). We investigate the problem of determining the total detection numbers of cycles.

MSC:

05C15 Coloring of graphs and hypergraphs
05C38 Paths and cycles
05C45 Eulerian and Hamiltonian graphs
05C78 Graph labelling (graceful graphs, bandwidth, etc.)

References:

[1] M. Aigner and E. Triesch, Irregular assignments and two problems à la Ringel , in: Topics in Combinatorics and Graph Theory, R. Bodendiek and R. Henn (Ed(s)), (Heidelberg: Physica, 1990) 29-36.; · Zbl 0752.05034
[2] M. Aigner, E. Triesch and Zs. Tuza, Irregular assignments and vertex-distinguishing edge-colorings of graphs, in: Combinatorics ’90, (New York: Elsevier Science Pub., 1992) 1-9.; · Zbl 0769.05035
[3] A.C. Burris, On graphs with irregular coloring number 2, Congr. Numer. 100 (1994) 129-140.; · Zbl 0836.05029
[4] A.C. Burris, The irregular coloring number of a tree, Discrete Math. 141 (1995) 279-283. doi:10.1016/0012-365X(93)E0225-S; · Zbl 0829.05027
[5] G. Chartrand, H. Escuadro, F. Okamoto and P. Zhang, Detectable colorings of graphs, Util. Math. 69 (2006) 13-32.; · Zbl 1102.05020
[6] G. Chartrand, L. Lesniak and P. Zhang, Graphs and Digraphs (CRC Press, Boca Raton, FL, 2010).; · Zbl 1329.05001
[7] H. Escuadro, F. Fujie and C.E. Musick, On the total detection numbers of complete bipartite graphs, Discrete Math. 313 (2013) 2908-2917. doi:10.1016/j.disc.2013.09.001; · Zbl 1281.05120
[8] H. Escuadro and F. Fujie-Okamoto, The total detection numbers of graphs, J. Com- bin. Math. Combin. Comput. 81 (2012) 97-119.; · Zbl 1252.05060
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.