Trees with Distinguishing Index Equal Distinguishing Number Plus One
The distinguishing number (index) D(G) (D′ (G)) of a graph G is the least integer d such that G has an vertex (edge) labeling with d labels that is preserved only by the trivial automorphism. It is known that for every graph G we have D′ (G) ≤ D(G) + 1. In this note we characterize finite trees for...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
University of Zielona Góra
2020-08-01
|
| Series: | Discussiones Mathematicae Graph Theory |
| Subjects: | |
| Online Access: | https://doi.org/10.7151/dmgt.2162 |
| _version_ | 1827844654628864000 |
|---|---|
| author | Alikhani Saeid Klavžar Sandi Lehner Florian Soltani Samaneh |
| author_facet | Alikhani Saeid Klavžar Sandi Lehner Florian Soltani Samaneh |
| author_sort | Alikhani Saeid |
| collection | DOAJ |
| description | The distinguishing number (index) D(G) (D′ (G)) of a graph G is the least integer d such that G has an vertex (edge) labeling with d labels that is preserved only by the trivial automorphism. It is known that for every graph G we have D′ (G) ≤ D(G) + 1. In this note we characterize finite trees for which this inequality is sharp. We also show that if G is a connected unicyclic graph, then D′ (G) = D(G). |
| first_indexed | 2024-03-12T08:44:59Z |
| format | Article |
| id | doaj.art-89de7e86ea3f40d49c99535268227aa4 |
| institution | Directory Open Access Journal |
| issn | 2083-5892 |
| language | English |
| last_indexed | 2024-03-12T08:44:59Z |
| publishDate | 2020-08-01 |
| publisher | University of Zielona Góra |
| record_format | Article |
| series | Discussiones Mathematicae Graph Theory |
| spelling | doaj.art-89de7e86ea3f40d49c99535268227aa42023-09-02T16:29:33ZengUniversity of Zielona GóraDiscussiones Mathematicae Graph Theory2083-58922020-08-0140387588410.7151/dmgt.2162dmgt.2162Trees with Distinguishing Index Equal Distinguishing Number Plus OneAlikhani Saeid0Klavžar Sandi1Lehner Florian2Soltani Samaneh3Department of Mathematics, Yazd University, 89195-741, Yazd, IranFaculty of Mathematics and Physics, University of Ljubljana, Slovenia, Faculty of Natural Sciences and Mathematics, University of Maribor, Slovenia, Institute of Mathematics, Physics and Mechanics, Ljubljana, SloveniaMathematics Institute, University of Warwick, Coventry, United KingdomDepartment of Mathematics, Yazd University, 89195-741, Yazd, IranThe distinguishing number (index) D(G) (D′ (G)) of a graph G is the least integer d such that G has an vertex (edge) labeling with d labels that is preserved only by the trivial automorphism. It is known that for every graph G we have D′ (G) ≤ D(G) + 1. In this note we characterize finite trees for which this inequality is sharp. We also show that if G is a connected unicyclic graph, then D′ (G) = D(G).https://doi.org/10.7151/dmgt.2162automorphism groupdistinguishing indexdistinguishing numbertreeunicyclic graph05c1505e18 |
| spellingShingle | Alikhani Saeid Klavžar Sandi Lehner Florian Soltani Samaneh Trees with Distinguishing Index Equal Distinguishing Number Plus One Discussiones Mathematicae Graph Theory automorphism group distinguishing index distinguishing number tree unicyclic graph 05c15 05e18 |
| title | Trees with Distinguishing Index Equal Distinguishing Number Plus One |
| title_full | Trees with Distinguishing Index Equal Distinguishing Number Plus One |
| title_fullStr | Trees with Distinguishing Index Equal Distinguishing Number Plus One |
| title_full_unstemmed | Trees with Distinguishing Index Equal Distinguishing Number Plus One |
| title_short | Trees with Distinguishing Index Equal Distinguishing Number Plus One |
| title_sort | trees with distinguishing index equal distinguishing number plus one |
| topic | automorphism group distinguishing index distinguishing number tree unicyclic graph 05c15 05e18 |
| url | https://doi.org/10.7151/dmgt.2162 |
| work_keys_str_mv | AT alikhanisaeid treeswithdistinguishingindexequaldistinguishingnumberplusone AT klavzarsandi treeswithdistinguishingindexequaldistinguishingnumberplusone AT lehnerflorian treeswithdistinguishingindexequaldistinguishingnumberplusone AT soltanisamaneh treeswithdistinguishingindexequaldistinguishingnumberplusone |