Distinguishing numbers and distinguishing indices of oriented graphs

DOI10.1016/J.DAM.2020.06.007zbMATH Open1450.05075arXiv1910.12738OpenAlexW3034595766MaRDI QIDQ2197442FDOQ2197442

Authors: Kahina Meslem, Éric Sopena 

Publication date: 31 August 2020

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: A distinguishing r-vertex-labelling (resp. r-edge-labelling) of an undirected graph G is a mapping $lambda$ from the set of vertices (resp. the set of edges) of G to the set of labels {1,. .. , r} such that no non-trivial automorphism of G preserves all the vertex (resp. edge) labels. The distinguishing number D(G) and the distinguishing index D (G) of G are then the smallest r for which G admits a distinguishing r-vertex-labelling or r-edge-labelling, respectively. The distinguishing chromatic number D $chi$ (G) and the distinguishing chromatic index D $chi$ (G) are defined similarly, with the additional requirement that the corresponding labelling must be a proper colouring. These notions readily extend to oriented graphs, by considering arcs instead of edges. In this paper, we study the four corresponding parameters for oriented graphs whose underlying graph is a path, a cycle, a complete graph or a bipartite complete graph. In each case, we determine their minimum and maximum value, taken over all possible orientations of the corresponding underlying graph, except for the minimum values for unbalanced complete bipartite graphs K m,n with m = 2, 3 or 4 and n > 3, 6 or 13, respectively, or m $ge$ 5 and n > 2 m -- m 2 , for which we only provide upper bounds.

Full work available at URL: https://arxiv.org/abs/1910.12738

Recommendations

• Distinguishing number and distinguishing index of certain graphs
• The chromatic distinguishing index of certain graphs
• The distinguishing chromatic number of line graphs of complete graphs
• Breaking the symmetries of the book graph and the generalized Petersen graph
• Distinguishing graphs by edge-colourings

zbMATH Keywords

automorphism grouporiented graphcomplete bipartite graphdistinguishing chromatic numberdistinguishing numberdistinguishing indexdistinguishing chromatic index

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Cites Work

• Symmetry breaking in graphs
• Destroying symmetry by orienting edges: Complete graphs and complete bigraphs
• Trivial Set-Stabilizers in Finite Permutation Groups
• On computing the distinguishing and distinguishing chromatic numbers of interval graphs and other results
• Distinguishing number of countable homogeneous relational structures
• The distinguishing number of Cartesian products of complete graphs
• On Computing the Distinguishing Numbers of Planar Graphs and Beyond: A Counting Approach
• The distinguishing chromatic number
• Finite factors of Bernoulli schemes and distinguishing labelings of directed graphs
• Distinguishing graphs by edge-colourings
• Distinguishing colorings of Cartesian products of complete graphs
• Distinguishing Cartesian products of countable graphs
• Distinguishing Cartesian powers of graphs
• Distinguishing Cartesian powers of graphs
• Cartesian powers of graphs can be distinguished by two labels
• Title not available (Why is that?)
• The distinguishing number of the hypercube
• The distinguishing number and distinguishing index of the lexicographic product of two graphs
• Symmetries of partial Latin squares
• Identity orientation of complete bipartite graphs
• Automorphism free Latin square graphs
• Symmetry breaking in tournaments
• On the distinguishing number of cyclic tournaments: towards the Albertson-Collins conjecture
• Distinguishing number and distinguishing index of neighbourhood corona of two graphs

Cited In (9)

• Distinguishing index of maps
• The distinguishing number (index) and the domination number of a graph
• Breaking the symmetries of the book graph and the generalized Petersen graph
• Extremal graphs for the distinguishing index
• Distinguishing arc-colourings of symmetric digraphs
• Distinguishing tournaments with small label classes
• Symmetry breaking in planar and maximal outerplanar graphs
• Proper distinguishing arc-colourings of symmetric digraphs
• The distinguishing number and the distinguishing index of line and graphoidal graph(s)

This page was built for publication: Distinguishing numbers and distinguishing indices of oriented graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2197442)