×

Nordhaus-Gaddum type inequalities for the distinguishing index. (English) Zbl 1485.05068

Summary: The distinguishing index of a graph \(G\), denoted by \(D'(G)\), is the least number of colours in an edge colouring of \(G\) not preserved by any nontrivial automorphism. This invariant is defined for any graph without \(K_2\) as a connected component and without two isolated vertices, and such a graph is called admissible. We prove the Nordhaus-Gaddum type relation: \[ 2 \leq D^{\prime}(G) + D^{\prime}(\overline{G}) \leq \Delta (G) + 2 \] for every admissible connected graph \(G\) of order \( |G| \geq 7\) such that \(\overline{G}\) is also admissible.

MSC:

05C15 Coloring of graphs and hypergraphs
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
05C30 Enumeration in graph theory
05C35 Extremal problems in graph theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] M. Aouchiche and P. Hansen, A survey of Nordhaus-Gaddum type relations,Discrete Appl. Math.161(2013), 466-546, doi:10.1016/j.dam.2011.12.018. · Zbl 1259.05083
[2] J. A. Bondy and V. Chv´atal, A method in graph theory,Discrete Math.15(1976), 111-135, doi:10.1016/0012-365x(76)90078-9. · Zbl 0331.05138
[3] K. L. Collins and A. N. Trenk, Nordhaus-Gaddum theorem for the distinguishing chromatic number,Electron. J. Combin.20(2013), #P46 (18 pages), doi:10.37236/2117. · Zbl 1298.05112
[4] M. J. Fisher and G. Isaak, Distinguishing colorings of Cartesian products of complete graphs, Discrete Math.308(2008), 2240-2246, doi:10.1016/j.disc.2007.04.070. · Zbl 1147.05029
[5] S. M. Hedetniemi, S. T. Hedetniemi and P. J. Slater, A note on packing two trees intoKN,Ars Combin.11(1981), 149-153. · Zbl 0491.05050
[6] W. Imrich, J. Jerebic and S. Klavˇzar, The distinguishing number of Cartesian products of complete graphs,European J. Combin.29(2008), 922-929, doi:10.1016/j.ejc.2007.11.018. · Zbl 1205.05198
[7] W. Imrich, R. Kalinowski, M. Pil´sniak and M. Wo´zniak, The distinguishing index of connected graphs without pendant edges,Ars Math. Contemp.18(2020), 117-126, doi:10.26493/ 1855-3974.1852.4f7. · Zbl 1464.05152
[8] R. Kalinowski and M. Pil´sniak, Distinguishing graphs by edge-colourings,European J. Combin.45(2015), 124-131, doi:10.1016/j.ejc.2014.11.003. · Zbl 1304.05046
[9] E. A. Nordhaus and J. W. Gaddum, On complementary graphs,Amer. Math. Monthly63(1956), 175-177, doi:10.2307/2306658. · Zbl 0070.18503
[10] M. Pil´sniak, Improving upper bounds for the distinguishing index,Ars Math. Contemp.13 (2017), 259-274, doi:10.26493/1855-3974.981.ff0. · Zbl 1380.05028
[11] V. G. Vizing, The chromatic class of multigraphs,Kibernetika (Kiev)1(1965), 29-39. · Zbl 0166.19601
[12] A. A. Zykov, On some properties of linear complexes,Mat. Sb. (N.S.)24(1949), 163-188, http://mi.mathnet.ru/eng/msb5974 · Zbl 0033.02602
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.