Distinguishing critical graphs. Issue 3 (3rd April 2021)

• Record Type: Journal Article
• Authors: Alikhani, Saeid; Soltani, Samaneh
• Is Part Of: Journal of information & optimization sciences. Volume 42:Issue 3(2021)
• Page Start: 655
• Page End: 668
• Publication Date: 2021-04-03
• Subjects: 05C15 -- 05E18; Distinguishing -- Critical -- Graph; Electronic data processing -- Periodicals; Information science -- Periodicals; Mathematical optimization -- Periodicals; 519.6
• DOI: 10.1080/02522667.2020.1773614
• Languages: English
• ISSNs: 0252-2667

Abstract

Abstract: The distinguishing number D ( G ) of a graph G is the least integer d such that G has a vertex labeling with d labels that is preserved only by a trivial automorphism. We say that a graph G is d -distinguishing critical, if D ( G ) = d and D ( H ) ≠ D ( G ), for every proper induced subgraph H of G . This generalizes the usual definition of a d -chromatic critical graph. While the investigation of d -critical graphs is a well established part of coloring theory, not much is known about d -distinguishing critical graphs. In this paper we determine all d -distinguishing critical graphs for d = 1, 2, 3 and observe that all of these kind of graphs are k -regular graph for some k ≤ d . Also, we state some results about the disconnected d -distinguishing critical graph with c connected components such that .