Distinguishing numbers and distinguishing indices of oriented graphs

DOI10.1016/J.DAM.2020.06.007MaRDI QIDQ2197442zbMATH OpenOpenAlexFDO

Authors Kahina Meslem, Éric Sopena

Publication date 31 August 2020

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

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

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)

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.

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

Cites work

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

Cited in

(9)

• The distinguishing number and the distinguishing index of line and graphoidal graph(s)
• 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

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)