The Distinguishing Number and the Distinguishing Index of Graphs from Primary Subgraphs

Document Type : Research Paper


1 Yazd University, Yazd, Iran

2 Department of Mathematics, Yazd University, 89195-741, Yazd, Iran


The distinguishing number (index) D(G) (D'(G)) of a graph G is the least integer d such that G has an vertex labeling (edge labeling) with d labels that is preserved only by a trivial automorphism. Let G be a connected graph constructed from pairwise disjoint connected graphs G1,... ,Gk by selecting a vertex of G1, a vertex of G2, and identifying these two vertices. Then continue in this manner inductively. We say that G is obtained by point-attaching from G1, ... ,Gk and that Gi's are the primary subgraphs of G.  In this paper, we consider some particular cases of these graphs that are of importance in chemistry and study their distinguishing number and distinguishing index.


  1. M.O. Albertson and K.L. Collins, Symmetry breaking in graphs, Electron. J. Combin. 3 (1996) #R18.
  2. S. Alikhani and S. Soltani, Distinguishing number and distinguishing index of certain graphs, Filomat 31 (14) (2017) 4393–4404.
  3. E. Deutsch and S. Klavžar, Computing Hosoya polynomials of graphs from primary subgraphs, MATCH Commun. Math. Comput. Chem. 70 (2013) 627–644.
  4. M. V. Diudea, I. Gutman and J. Lorentz, Molecular Topology, Nova Science Publishers, Huntington, N.Y, 2001.
  5. M. Ghorbani and M. A. Hosseinzadeh, On Wiener index of special case of link of fullerenes, Optoelectr. Adv. Mater. Rapid Comm. 4 (2010) 538–539.
  6. M. Ghorbani and M. Songhori, Some topological indices of nanostar dendrimers, Iranian J. Math. Chem. 1 (2010) 57–65.
  7. R. Hammack, W. Imrich and S. Klavžar, Handbook of product graphs (second edition), Taylor & Francis group, 2011.
  8. R. Kalinowski and M. Pilśniak, Distinguishing graphs by edge colourings, European J. Combin. 45 (2015) 124–131.
  9. T. Mansour and M. Schork, The PI index of bridge and chain graphs, MATCH Commun. Math. Comput. Chem. 61 (2009) 723–734.
  10. T. Mansour and M. Schork, Wiener, hyper-Wiener, detour and hyper-detour indices of bridge and chain graphs, J. Math. Chem. 47 (2010) 72–98.
  11. H. Wiener, Structural determination of paraffin boiling points. J. Am. Chem. Soc. 69 (1947) 17–20.