![MathJax Logo](/templates/jsp/_style2/_tandf/pb2/images/math-jax.gif)
Abstract
The distinguishing number (index) (
) of a graph
is the least integer
such that
has a vertex labeling (edge labeling) with
labels that is preserved only by a trivial automorphism. A graphoidal cover of
is a collection
of (not necessarily open) paths in
such that every path in
has at least two vertices, every vertex of
is an internal vertex of at most one path in
and every edge of
is in exactly one path in
. Let
denote the intersection graph of
. A graph
is called a graphoidal graph, if there exist a graph
and a graphoidal cover
of
such that
. In this paper, we study the distinguishing number and the distinguishing index of the line graph and the graphoidal graph of a simple connected graph
.
1 Introduction and definitions
Let be a simple, finite, connected and undirected graph, and let
be its automorphism group.A labeling of
,
, is said to be
-distinguishing, if no non-trivial automorphism of
preserves all of the vertex labels. The point of the labels on the vertices is to destroy the symmetries of the graph, that is, to make the automorphism group of the labeled graph trivial. Formally,
is
-distinguishing if for every non-identity
, there exists
in
such that
. The distinguishing number of a graph
is defined by
This number was defined in [Citation1]. Similar to this definition, in [Citation2] the distinguishing index of
, which is the least integer
such that
has an edge coloring with
colors that is preserved only by a trivial automorphism, has been defined.
can be arbitrary smaller than
, for example
and
, for
.
The line graph of a graph
is the graph whose vertices are edges of
and two edges
are adjacent if they share an endpoint. The line graphs can be viewed a special case of graphoidal graphs. The concept of graphoidal cover was introduced by Acharya and Sampathkumar [Citation3].
Definition 1.1
[Citation3] A graphoidal cover of a graph is a collection
of (not necessarily open) paths in
satisfying the following conditions:
(i) | Every path in | ||||
(ii) | Every vertex of | ||||
(iii) | Every edge of |
Definition 1.2
[Citation3] If is a family of distinct nonempty subsets of a set
, whose union is
, then the intersection graph of
, denoted by
, is the graph whose vertex set and edge set are given by
Let be the set of all graphoidal covers of
and
. The intersection graph on
is denoted by
. A graph
is called a graphoidal graph if there exist a graph
and
such that
. Since
is obviously a graphoidal cover of
, all line graphs are graphoidal graphs. In [Citation3] Acharya and Sampathkumar have proved that all the Beineke’s forbidden subgraphs of line graphs (see ) are graphoidal graphs and hence they conjectured that all graphs are graphoidal. In [Citation4] Arumugam and Pakkiam disproved this conjecture by showing that complete bipartite graphs
with
are not graphoidal graphs. They also obtained a forbidden subgraph characterization of all bipartite graphs which are graphoidal. Note that if
is a path, not necessarily open, in a graph
, then
and
are called terminal vertices and
are called internal vertices of
. For cycles (considered as closed paths), there is an inherent “ordering” of vertices as in paths. So, when we say that a cycle
of a graph
is a member of a graphoidal cover
of
, we should mention the vertex at which the cycle
begins, and this particular vertex is considered as the terminal vertex of
and all other vertices on
are called internal vertices of
. Given a graphoidal cover
of
, a vertex
is said to be interior to
if
is an internal vertex of an element of
and is called exterior to
otherwise.
In the next section, we study the distinguishing number and the distinguishing index of line graphs. In Section 3, we consider graphoidal graphs and study their distinguishing number and distinguishing index.
2 Study of ![](//:0)
and ![](//:0)
for the line graphs
For a simple graph , line graph
is the graph whose vertices are edges of
and two edges
are adjacent if they share an endpoint in common. The following theorem characterizes the line graphs.
Theorem 2.1
[Citation5] The following statements are equivalent for a graph .
(i) | The graph | ||||
(ii) | The edges of | ||||
(iii) | The graph | ||||
(iv) | None of the nine graphs in is an induced subgraph of |
To study the distinguishing number and the distinguishing index of , we need more information about the automorphism group of
. Let
be given by
for every
. In [Citation6], Sabidussi proved the following theorem which we need later.
Theorem 2.2
[Citation6] If is a connected graph that is not
, or
, which is
with one edge removed, (see ), then
is a group isomorphism, and so
.
Fig. 2 Graphs and
of Theorem 2.2.
![Fig. 2 Graphs Q and L(Q) of Theorem 2.2.](/cms/asset/769eccbc-df99-4c73-888b-9a13a323d0ea/uakc_a_1755561_f0002_b.jpg)
Now we are ready to obtain the distinguishing number of line graph of a graph. We note that if , then it is easy to see that
, while
.
Theorem 2.3
If is a connected graph that is not
or
, then
.
Proof
If , then it is easy to see that
. If
, first we show that
. Let
be an edge distinguishing labeling of
. We define
such that
, where
. The vertex labeling
is a distinguishing vertex labeling of
, because if
is an automorphism of
preserving the labeling, then
, and hence
for any
. On the other hand, by Theorem 2.2,
for some automorphism
of
. Thus from
for any
, we can conclude that
and so
for every
. This means that
is an automorphism of
preserving the labeling
, and so
is the identity automorphism of
. Therefore
is the identity automorphism of
, and hence
. For the converse, suppose that
is a vertex distinguishing labeling of
). We define
such that
where
. The edge labeling
is a distinguishing edge labeling of
. Because if
is an automorphism of
preserving the labeling, then
, and hence
for any
. Then, there exists an automorphism
of
such that
for every
, by Theorem 2.2. Thus from
for any
, we can conclude that
for every
, which means that
preserves the distinguishing vertex labeling of
, and hence
is the identity automorphism of
. Therefore
is the identity automorphism of
, and so
.
An upper bound for the distinguishing index of line graphs follows immediately from the following result of Pilśniak in [Citation7]. A -free graph, called also a claw-free graph, is a graph that does not contain a copy of
as an induced subgraph.
Theorem 2.4
[Citation7] If is a connected claw-free graph, then
.
Now by Part (iii) of Theorems 2.1 and 2.4, we have the following theorem.
Theorem 2.5
If is a connected graph, then
.
3 Study of ![](//:0)
and ![](//:0)
for graphoidal graphs
We recall that a graphoidal cover of a graph is a collection
of (not necessarily open) paths in
satisfying the following conditions: every path in
has at least two vertices, every vertex of
is an internal vertex of at most one path in
, and every edge of
is in exactly one path in
. Let
be a graphoidal cover of
and
denote the intersection graph of
. Thus the vertices of
are the paths in
and two paths in
are adjacent in
if and only if they have a common vertex. A graph
is said to be graphoidal if there exist a graph
and a graphoidal cover
of
such that
is isomorphic to
. First we state and prove the following theorem:
Theorem 3.1
For any positive integer there exists a graph
with a graphoidal cover
for which
and
.
Proof
Let be a graph as shown in . It is easy to see that
. A graphoidal cover of
is
where
and
for
. Thus
, and hence
. Therefore we have the result.
Fig. 3 Graph in the proof of Theorem 3.1.
![Fig. 3 Graph G in the proof of Theorem 3.1.](/cms/asset/30f790e0-cf26-4912-b2d6-6c907d238d66/uakc_a_1755561_f0003_b.jpg)
To study the distinguishing index of graphoidal graphs, we need some theorems.
Theorem 3.2
[Citation2] If is a connected graph of order
, then
, unless
is
or
.
Recall that every finite tree has either a central vertex or a central edge, which is fixed by every automorphism of
. A symmetric tree, denoted by
, is a tree with a central vertex
, all leaves at the same distance
from
and all the vertices which are not leaves with degree
. A bisymmetric tree, denoted by
, is a tree with a central edge
, all leaves at the same distance
from
and all the vertices which are not leaves with degree
.
Theorem 3.3
[Citation7] Let be a connected graph that is neither a symmetric nor a bisymmetric tree. If the maximum degree of
is at least 3, then
, unless
is
or
.
Theorem 3.4
[Citation8] If is a tree of order
, then
. Furthermore, equality is achieved if and only if
is a symmetric tree or a path of odd length.
Before we state the next theorem we need to define some terms: Let be a vertex of a graph
and let
be a
-distinguishing edge labeling of
. We say that f is
-distinguishing if
is preserved only by the trivial automorphism among the automorphisms
for which
holds. If
is an edge of a tree
, then let
and
be the components of
with
and
. A family
consists of those trees
of order at least 3, for which the following conditions are fulfilled: (1)
is a bicentric tree with the central edge
, (2)
and
are isomorphic trees, (3)
admits a unique
-distinguishing edge
-labeling.
Theorem 3.5
[Citation9] Let be a tree of order
. Then
if
, and
otherwise.
Now, we obtain bounds for the distinguishing index of graphoidal graphs.
Theorem 3.6
Let be a connected graph and
be a graphoidal cover of
such that the order of
is at least
. If
, then
Moreover,
if and only if
is
,
or
.
Proof
By , we can conclude the left inequality. For the right inequality, by contradiction, we suppose that . Since
by Theorem 3.2, we get
, which is a contradiction, since
.
If , then
, by Theorem 3.2, unless for
. If
, then we have
, if and only if
is a symmetric, a bisymmetric tree,
or
, by Theorem 3.3. Now since
,
if and only if
is
,
or
, by Theorems 3.4 and 3.5.
Fig. 4 The graph and its graphoidal of Theorem 3.7.
![Fig. 4 The graph G and its graphoidal of Theorem 3.7.](/cms/asset/ad28c997-44de-4883-8bd0-9a9401e1df48/uakc_a_1755561_f0004_b.jpg)
Fig. 5 An example for sharpness of inequality of Theorem 3.9.
![Fig. 5 An example for sharpness of inequality of Theorem 3.9.](/cms/asset/2a8b1771-91d9-4f41-81f9-670c1ad69703/uakc_a_1755561_f0005_b.jpg)
The following theorem states that for every ,
, there exists a connected graphoidal graph with the distinguishing index
.
Theorem 3.7
Suppose that and
are positive integers and
. If
and
, then there exist a graph
of order
and graphoidal cover
of
with
such that
.
Proof
Let be a graph in . If
where
and for every
,
,
for each
, then
is as shown in . It is easy to compute that
. With respect to integers
and
, we get that
.
In the sequel, we give bounds for the distinguishing number of the graphoidal graphs.
Theorem 3.8
Let be a connected graph of order
. Then
Proof
Since has
vertices, it is clear that
. To prove the left inequality, let
and
,
be the set of vertices of
having label
in the distinguishing labeling of
. Now we want to label the edges of
distinguishingly, using
labels. For this purpose, for every
,
, we label the edge set of all paths of
(not necessarily open) in
of length
with
-tuple
of labels. We note that since there exist the closed paths (cycles) in
, we need at most three different labels to distinguishing these closed paths. Then we have an edge labeling of
with
labels. To show that this edge labeling is distinguishing, we prove that if
is an automorphism of
preserving this edge labeling, then
maps
to
, setwise. In fact, if
, then
is a path of the same length as
. Since
preserves the edge labeling of
, the label of edges of
is the same as edges of
. With respect to the method of labeling of edge set of each path in
, we conclude that
. Hence
maps a path in
to a path in
. Thus
can be considered as an automorphism of
preserves the distinguishing vertex labeling of
with
labels. Thus
is the identity automorphism of
, and this means that
for all
. On the other hand, since we labeled the edge set of each path in
distinguishingly with at most three labels, so
fixes all vertices of path
, where
. Thus
is the identity automorphism of
.
The bounds of Theorem 3.8 are sharp. For the left inequality, it is sufficient to consider ,
, and
. Thus
, and hence
and
. To show that the upper bound of this theorem is sharp, we consider
and
. Thus
, and hence
and
.
Theorem 3.9
If is a connected graph of order
and the graphoidal cover
of
contains only open paths, then
.
Proof
The proof is exactly the same as proof of Theorem 3.8, except the method of labeling of edges of paths in . Since all paths in
are open, then by notation of Theorem 3.8, for every
,
, we label the edge set of all open paths of
in
of length
with the
-tuple
of labels. Then we have an edge labeling of
with
labels. To show this edge labeling is distinguishing, we prove that if
is an automorphism of
preserving this edge labeling, then
maps
to
setwise. In fact, if
, then
is a path of the same length as
. Since
preserves the edge labeling of
, the label of edges of
is the same as edges of
. With respect to the method of labeling of edge set of each path in
, we conclude that
. Hence
maps a path in
to a path in
. Thus
can be considered as an automorphism of
preserves the distinguishing vertex labeling of
with
labels. Thus
is the identity automorphism of
, and this means that
for all
. On the other hand, since we labeled the edge set of each path in
distinguishingly with at most two labels,
fixes all vertices of path
where
. Thus
is the identity automorphism of
.
The bound of Theorem 3.9 is sharp. Let be as shown in . It is easy to obtain that
. A graphoidal cover of
is
where
,
,
,
,
,
, and
. Thus
is an asymmetric graph, and hence
.
We conclude the paper with the following theorem, which shows that the value can be arbitrary.
Theorem 3.10
For every ,
, there exist a connected graph
and a graphoidal cover
of
such that
.
Proof
Let and
be the two graphs of Theorem 3.7. Since the automorphism group of
has at most one nonidentity automorphism,
. On the other hand
is a tree with a central vertex, and so
, by Theorem 3.5. Now, with respect to the values of
and
, we obtain the result.
References
- AlbertsonM.O., CollinsK.L., Symmetry breaking in graphs, Electron. J. Combin., 3 1996 #R18
- KalinowskiR., PilśniakM., Distinguishing graphs by edge colourings, European J. Combin., 45 2015 124–131
- AcharyaB.D., SampathkumarE., Graphoidal covers and graphoidal covering number of a graph, Indian J. Pure Appl. Math., 18101987 882–890
- ArumugamS., PakkiamC., Graphoidal bipartite graphs, Graphs Combin., 10 1994 305–310
- BeinekeL.W., Characterizations of derived graphs, J. Combin. Theory, 921970 129–135
- SabidussiG., Graph derivatives, Math. Z., 76 1961 385–401
- PilśniakM., Improving upper bounds for the distinguishing index, Ars Math. Contemp., 13 2017 259–274
- CollinsK.L., TrenkA.N., The distinguishing chromatic number, Electron. J. Combin., 13 2006 #R16
- S. Alikhani, S. Klav̌zar, F. Lehner, S. Soltani, Trees with distinguishing index equal distinguishing number plus one,arXiv:1608.03501v4 [math.CO].