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 groupcomplete bipartite graphdistinguishing chromatic indexdistinguishing chromatic numberdistinguishing indexdistinguishing numberoriented graph

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.

Review text

A distinguishing $r$-vertex labeling ($r$-edge labeling) of an undirected graph $G$ is a mapping \(\lambda\) from the set of vertices (the set of edges) of $G$ to the set of labels $\{1,2,\dots,r\}$ such that no non-trivial automorphism of $G$ preserves all the vertex (edge) labels. The distinguishing number $D(G)$ and the distinguishing index \(D^\prime ( G )\) of $G$ are then the smallest $r$ for which $G$ admits a distinguishing $r$-vertex labeling or $r$-edge labeling respectively. The distinguishing chromatic number \(D_\chi ( G )\) and the distinguishing chromatic index \(D_{\chi^\prime} ( G )\) are defined similarly, with the additional requirement that the corresponding labeling must be a proper coloring. An oriented graph is a digraph with no loops and no pairs of opposite arcs. In this paper, the authors give four parameters for oriented graphs whose underlying graph is a path, a cycle, a complete graph or a complete bipartite graph. Also, they find the minimum and maximum values, 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 \geq 5\) and \(n > 2^m - \left\lceil \frac{ m}{ 2}\right\rceil \), for which they provide the upper bounds only.

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

• 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
• scientific article; zbMATH DE number 1439496 (Why is no real title available?)
• Identity orientation of complete bipartite graphs
• On computing the distinguishing and distinguishing chromatic numbers of interval graphs and other results
• On Computing the Distinguishing Numbers of Planar Graphs and Beyond: A Counting Approach
• 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

(11)

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

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)